8种常用的排序算法(Java版)

喜欢ヅ旅行 2022-01-09 11:13 301阅读 0赞

目前常用的排序算法有8种，下图为各种排序算法的分类，方便记忆。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70]  
下面详细说明每一种算法的思想（每一种默认为从小到大排序）：

# 1. 直接插入排序 #

该排序算法是在已经有序的序列中寻找待插入数值的位置，然后将该数值插入即可。  
![在这里插入图片描述][20190622105905994.PNG_pic_center]  
如上图所示，arr为待排序数组，将每一个待排序的数字与之前已经排好序的序列进行比较，将所有比它大的数都后移一位，后移完成后，空出来的位置即为该数字所在的位置。

public void insertSort(int[] arr) {
    		for (int i = 1; i < arr.length; i++) {//外循环，决定总共的循环次数
    			for (int j = i - 1; j >= 0; j--) {//内循环，进行数值的比较和移位
    				if (arr[i] < arr[j]) {
    					int temp = arr[i];
    					arr[i] = arr[j];
    					arr[j] = temp;
    				}
    			}
    		}
    		for (int item : arr) {
    			System.out.print(item + " ");
    		}
    	}

# 2. 二分插入排序（折半插入排序） #

在已排序的序列中定义三个指针left、mid、right，分别指向该队列的最左端、中间和最右边。将待排序的数与mid指针所指向的数进行比较，从而更新left、mid、right指针的指向，直到right<left时，left指针指向的位置即为待插入数插入的位置。

public void binaryInsertSort(int[] arr) {
    		for (int i = 0; i < arr.length; i++) {
    			int temp = arr[i];//定义临时变量，记录带插入数
    			int left = 0;//已排序序列的初始最左边
    			int right = i - 1;//已排序序列的初始最右边
    			int mid = 0;//已排序序列的初始中间值
    			//通过将待插入数tmep与arr[mid]比较从而找到temp应该插入的位置，即left
    			while (left <= right) {
    				mid = (left + right) / 2;
    				if (temp > arr[mid])
    					left = mid + 1;
    				else
    					right = mid - 1;
    			}
    			//left及left以后的数后移一位
    			for(int j=i-1;j>=left;j--) {
    				arr[j+1] = arr[j];
    			}
    			//若果left==i说明带插入的数arr[i]是最大的值，不需要进行插入，保持原位即可
    			if(left!=i) {
    				arr[left] = temp;
    			}
    		}
    		
    		for(int item:arr) {
    			System.out.print(item + " ");
    		}
    	}

# 3. 希尔排序 #

通过定义步长并将步长不断衰减至1，从而对序列进行跳跃式的排序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center]

/**
    	 * 希尔排序
    	 * 通过定义步长来跳跃式的排序，属于不稳定排序
    	 * @param arr
    	 */
    	public void shellSort(int[] arr) {
    		int step = arr.length/2;
    		while(step>=1) {
    			for(int i=0;i<arr.length;i++) {
    				for(int j=i+step;j<arr.length;j+=step) {
    					if(arr[j]<arr[i]) {
    						int temp = arr[j];
    						arr[j] = arr[i];
    						arr[i] = temp;
    					}
    				}
    			}
    			
    			step = step/2;
    		}
    		
    		for(int item:arr) {
    			System.out.print(item);
    		}
    	}

# 4. 冒泡排序 #

从待排序序列的第一个数开始，将数值大的数不断向后移动，就像“冒泡”一样，直到最大的数到达最后的位置。然后不断重复上述过程，直到完成排序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 1]

/**
    	 * 冒泡排序
    	 * 将数字大的不断向后冒泡，知道排到最后一位，然后前面n-1位继续循环操作。
    	 * @param arr
    	 */
    	public void bubbleSort(int[] arr) {
    		for(int i=0;i<arr.length-1;i++) {
    			for(int j=0;j<arr.length-1-i;j++) {
    				if(arr[j+1]<arr[j] ) {
    					int temp = arr[j+1];
    					arr[j+1] = arr[j];
    					arr[j] = temp;
    				}
    			}
    		}
    		
    		for(int item:arr) {
    			System.out.print(item);
    		}
    	}

# 5. 快速排序 #

定义低位指针和高位指针分别指向数组的第一个数和最后一个数，将基数指向低位指针所指的数。通过比较基数和高低位指针所指向的数的大小，不断的改变低位和高位指针的位置，当高低位指针重合时所指向的位置即为基数所应该存在的位置。将基数位置调整后，通过递归继续重复上述过程，即可完成排序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 2]

/**
    	 * 快速排序
    	 * 通过寻找基数的位置递归进行排序
    	 * @param arr
    	 * @param low 低位坐标
    	 * @param high 高位坐标
    	 */
    	public void quickSort(int[] arr,int low,int high) {
    		while(low<high) {
    			int middle = findMid(arr,low,high);
    			quickSort(arr,low,middle-1);
    			quickSort(arr,middle+1,high);
    		}
    		
    		for(int item:arr) {
    			System.out.print(item);
    		}
    	}
    
    	/**
    	 * 查找基数的坐标函数，当low=high时即找到了基数的坐标位置
    	 * @param arr
    	 * @param low
    	 * @param high
    	 * @return 返回基数应该在的位置
    	 */
    	private int findMid(int[] arr, int low, int high) {
    		int temp = arr[low];
    		while(low<high) {
    			while(low<high&&arr[high]>=temp) {
    				high--;
    			}
    			arr[low] = arr[high];
    			while(low<high&&arr[low]<=temp) {
    				low++;
    			}
    			arr[high] = arr[low];
    		}
    		
    		arr[low] = temp;
    		return low;
    	}

# 6. 直接选择排序 #

直接从待排序序列中选择最小的值与第一个数交换，再在n-1个数中选择最小的值，继续进行交换，直到排序完成。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 3]

/**
    	 * 直接选择排序
    	 * 从待排序序列中直接选择最小值与第一个位置的交换，以此类推与第二个、第三个位置交换，直到排序完成
    	 * @param arr
    	 */
    	public void selectSort(int[] arr) {
    		for(int i=0;i<arr.length-1;i++) {
    			for(int j=i+1;j<arr.length;j++) {
    				if(arr[j] < arr[i] ) {
    					int temp = arr[j] ;
    					arr[j] = arr[i];
    					arr[i] = temp;
    				}
    			}
    		}
    		
    		for(int item:arr) {
    			System.out.print(item);
    		}
    	}

# 7. 堆排序 #

### 堆的定义 ###

堆是一种特殊的完全二叉树，如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 4]  
可以看到，所有父结点都比子结点要小（注意：圆圈里面的数是值，圆圈上面的数是这个结点的编号，此规定仅适用于本节）。符合这样特点的完全二叉树我们称为最小堆（小顶堆）。反之，如果所有父结点都比子结点要大（大顶堆），这样的完全二叉树称为最大堆。

### 筛选法调整堆 ###

以小顶堆为例，调整过程如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 9]  
按照如上过程，将给出的随机序列调整成小顶堆或大顶堆，即完成了通过筛选法构建堆。

### 堆排序 ###

（1）将给定的随机序列构建成大顶堆；  
（2）将堆顶数与结尾数调换，则该序列的最后一位即为当前序列的最大值；  
（3）通过筛选法对前n-1个数进行堆调整，则使得堆顶数为n-1个数的最大值；  
（4）重复（2）（3）步骤，知道排序完成

/**
    	 * 堆排序
    	 * 先构建堆（大顶堆或小顶堆），然后通过将堆顶元素和堆底元素的不断调换，并通过筛选法调整堆来进行排序
    	 * @param arr
    	 */
    	public void heapSort(int[] arr) {
    		for(int i=arr.length/2-1;i>=0;i--) {
    			sift(arr,i,arr.length);
    		}
    		for(int i=arr.length-1;i>0;i--) {
    			int temp = arr[0];
    			arr[0] = arr[i];
    			arr[i] = temp;
    			sift(arr,0,i);
    		}
    		for(int item:arr) {
    			System.out.print(item + " ");
    		}
    	}
    
    	/**
    	 * 筛选法调整堆
    	 * @param arr
    	 * @param i 堆顶数字的序号
    	 * @param length 序列的长度
    	 */
    	private void sift(int[] arr,int i, int length) {
    		int top = i;
    		int left = 2*i + 1;
    		while(left<length) {
    			//找到左右孩子中较小的一个
    			if(left<length-1&&arr[left+1]>arr[left]) {
    				left ++;//指向右孩子
    			}
    			if(arr[top]<arr[left] ) {
    				int temp = arr[left];
    				arr[left] = arr[top];
    				arr[top] = temp;
    				top = left;
    				left = 2*top + 1;
    			}else {
    				left = length;
    			}
    		}
    	}

# 8. 归并排序 #

归并排序采用分治和递归的思想，先通过分治思想，将序列分解成n个单个的数。之后，通过递归的方式，将分解为单个数的n个数进行合并排序，如下图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70 1]

/**
    	 * 归并排序
    	 * 先将数组进行拆分，然后合并
    	 * @param arr
    	 * @param left
    	 * @param right
    	 */
    	public void mergeSort(int[] arr,int left,int right) {
    		if(left<right) {
    			int mid = (left+right)/2;
    			mergeSort(arr,left,mid);
    			mergeSort(arr,mid+1,right);
    			merge(arr,left,mid,right);
    		}
    		
    	}
    
    	/**
    	 * 通过left、mid和right可以将数组arr分割成两个小数组，从而进行合并
    	 * @param arr
    	 * @param left 左边数组的最左边下标
    	 * @param mid 左边数组的最右边下标
    	 * @param right 右边数组的最右边下标
    	 */
    	private void merge(int[] arr, int left, int mid, int right) {
    		int[] tempArr = new int[arr.length];
    		int rightStart = mid + 1;//右边数组的开始角标（即最左边下标）
    		int i = left;//指针，指向数组tempArr的角标
    		int tmp = left;
    		//找到两个数组中较小的值，并放入tempArr数组中
    		while(left<=mid&&rightStart<=right) {
    			if(arr[left]<=arr[rightStart]) {
    				tempArr[i++] = arr[left++];
    			}else {
    				tempArr[i++] = arr[rightStart++];
    			}
    		}
    		//如果左边数组没有放完，则将左边数组剩余的数放入tempArr中
    		while(left<=mid) {
    			tempArr[i++] = arr[left++];
    		}
    		//如果右边数组没有放完，则将右边数组剩余的数放入tempArr中
    		while(rightStart<=right) {
    			tempArr[i++] = arr[rightStart++];
    		}
    		//将临时数组中的数值放入到arr中
    		while(tmp<=right){
    			arr[tmp] = tempArr[tmp++];
    		}
    	}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70]: /images/20220109/049b783692eb41b3a149c1ea09c1ba96.png
[20190622105905994.PNG_pic_center]: /images/20220109/e3814601488347ceafad2c6069ba95c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center]: /images/20220109/d63dae6c66734d4aa7c68d950fa63432.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220109/bf9ebcef5d984bf493dc9ca4058f6567.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20220109/71cecd6ef9f145808e8a8acf49da67bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20220109/bcffb48219f14c08ba9d799277f7b9dc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20220109/d041d86dfac3427a830980192420133f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20220109/6aa56a4195094a25aaaf70ad9bf07633.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20220109/ded97760cb314c5085db38f1f262821d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20220109/2b31fd39ca8f46d688f4241a2ab6a2ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20220109/a6b9d10a5fdc47979503057b4c945b78.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20220109/99625716d63349238d5c1b9866d68cb9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3MDI0OA_size_16_color_FFFFFF_t_70 1]: /images/20220109/7f032b2f90d84a6b8d2a133d11a167b1.png