常见的八种排序方式

女爷i 2024-04-17 16:39 91阅读 0赞

### 八种排序的时间复杂度： ###

<table> 
 <tbody> 
  <tr> 
   <td>排序法</td> 
   <td>平均时间</td> 
   <td>最差情形</td> 
   <td>稳定度</td> 
   <td>额外空间</td> 
   <td>备注</td> 
  </tr> 
  <tr> 
   <td>冒泡</td> 
   <td>O(n2)</td> 
   <td>&nbsp;&nbsp;&nbsp; O(n2)</td> 
   <td>稳定</td> 
   <td>O(1)</td> 
   <td>n小时较好</td> 
  </tr> 
  <tr> 
   <td>选择</td> 
   <td>O(n2)</td> 
   <td>O(n2)</td> 
   <td>不稳定</td> 
   <td>O(1)</td> 
   <td>n小时较好</td> 
  </tr> 
  <tr> 
   <td>插入</td> 
   <td>O(n2)</td> 
   <td>O(n2)</td> 
   <td>稳定</td> 
   <td>O(1)</td> 
   <td>大部分已排序时较好</td> 
  </tr> 
  <tr> 
   <td>基数</td> 
   <td>O(logRB)</td> 
   <td>O(logRB)</td> 
   <td>稳定</td> 
   <td>O(n)</td> 
   <td> <p>B是真数(0-9)，</p> <p>R是基数(个十百)</p> </td> 
  </tr> 
  <tr> 
   <td>Shell</td> 
   <td>O(nlogn)</td> 
   <td>O(ns) 1&lt;s&lt;2</td> 
   <td>不稳定</td> 
   <td>O(1)</td> 
   <td>s是所选分组</td> 
  </tr> 
  <tr> 
   <td>快速</td> 
   <td>O(nlogn)</td> 
   <td>O(n2)</td> 
   <td>不稳定</td> 
   <td>O(nlogn)</td> 
   <td>n大时较好</td> 
  </tr> 
  <tr> 
   <td>归并</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>稳定</td> 
   <td>O(1)</td> 
   <td>n大时较好</td> 
  </tr> 
  <tr> 
   <td>堆</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>不稳定</td> 
   <td>O(1)</td> 
   <td>n大时较好</td> 
  </tr> 
 </tbody> 
</table>

### **冒泡排序**（Bubble Sort）**:** ###

传统的冒泡排序需要依次比较相邻的两个元素，按照升序或者降序的规则进行交换，如要让 3 2 1三个数进行升序排序，首先从3开始跟2比较大于2进行交换，然后在与1进行比较，进行交换，第一趟排序结果就是2 1 3；然后 2与1比较大于1交换，2与3比较小于3不变。这就是冒泡排序的原理。然而，如果是让 3 2 1进行降序排序呢，还要再从头到尾比较一边岂不是很浪费空间，此时我们就可以使用一个 flag标记来对冒泡排序进行排序。具体方法我们来看一下代码。

演示：

![20190828190943289.gif][]

代码：

**一般的冒泡排序：**

int arr[]={6,2,3,4,0};
            int change=0;
     
            for(int i=0;i<arr.length-1;i++){
                for(int j=0;j<arr.length-1-i;j++){
                    if(arr[j]>arr[j+1]){
                    
                        change=arr[j];
                        arr[j]=arr[j+1];
                        arr[j+1]=change;
                    }
                }
    
           
    
                System.out.println("第"+(i+1)+"趟"+Arrays.toString(arr));
            }

通过标记 flag来判断 是否进行了交换，如果没有则直接退出循环，从而达到了对排序的进一步优化。

**优化后的冒泡排序：**

int arr[]={6,2,3,4,0};
            int change=0;
            Boolean flag=false;
            for(int i=0;i<arr.length-1;i++){
                for(int j=0;j<arr.length-1-i;j++){
                    if(arr[j]>arr[j+1]){
                        flag=true;
                        change=arr[j];
                        arr[j]=arr[j+1];
                        arr[j+1]=change;
                    }
                }
    
                if(!flag){
                    break;
                }else {
                    flag=false;
                }
    
                System.out.println("第"+(i+1)+"趟"+Arrays.toString(arr));
            }

### 选择排序（Select Sort）： ###

第一次从待排序的[数据元素][Link 1]中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

假设序列第一个位置为最小，然后依次和后面的元素进行比较，比第一个元素小的元素就设个标记再往后依次比较，直到找到最小值然后与第一个位置元素进行交换。

演示：

![20190829103956425.gif][]

代码：

int[] arry= {7,4,8,3};
            for(int i = 0;i<arry.length-1;i++){
                int minIndex=i;
                int minArry=arry[i];
    
                for (int j = i+1;j<arry.length;j++){
                    if(minArry>arry[j]){
                        minIndex=j;
    
                        minArry=arry[j];
    
                    }
    
                }
                if(minIndex!=i){
                    arry[minIndex]=arry[i];
                    arry[i]=minArry;
                }
                System.out.println(Arrays.toString(arry));
            }

用过代码我们不难发现冒泡排序和选择排序的时间复杂度都是O(n²)，接下来我们看一下他们的区别：

（1）冒泡排序是比较相邻位置的两个数，而选择排序是按顺序比较，找最大值或者最小值；

（2）冒泡排序每一轮比较后，位置不对都需要换位置，选择排序每一轮比较都只需要换一次位置；

（3）冒泡排序是通过数去找位置，选择排序是给定位置去找数；

冒泡排序优缺点：优点:比较简单，空间复杂度较低，是稳定的；  
                              缺点:时间复杂度太高，效率慢；

选择排序优缺点：优点：一轮比较只需要换一次位置；

缺点：效率慢，不稳定（举个例子5，8，5，2，9   我们知道第一遍选择第一个元素5会和2交换，那么原序列中2个5的相对位置前后顺序就破坏了）

## ##

### 插入排序（Inser Sort）： ###

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。

在一个数组中我们开始把第一个元素看为是一个排好序的队列，剩余的看为是乱序的序列，在剩余的队列中依次选取元素与前面队列进行比较再尔进行排序，至此我们就保证前面的元素永远都是有序的，从而达到插入排序的效果。

演示：

![20190829160510706.gif][]

代码：

int arry[]={7,5,4,3,2};
    
            for(int i=1;i<arry.length;i++){
                int insertVal = arry[i];
                int insertIndex=i-1;
    
                while(insertIndex >= 0 && insertVal<arry[insertIndex]){
                    arry[insertIndex+1]=arry[insertIndex];
                    insertIndex--;
                }
                    arry[insertIndex+1]=insertVal;
          
                System.out.println(Arrays.toString(arry));
            }

优化后的代码：

优化后的代码我们可以发现，通过insertIndex是否变化 来判断while循环是否执行，从而避免不必要的赋值。

int arry[]={7,5,4,3,2};
    
            for(int i=1;i<arry.length;i++){
                int insertVal = arry[i];
                int insertIndex=i-1;
    
                while(insertIndex >= 0 && insertVal<arry[insertIndex]){
                    arry[insertIndex+1]=arry[insertIndex];
                    insertIndex--;
                }
                if(insertIndex+1!=i){ //此时无需交换
                    arry[insertIndex+1]=insertVal;
                }
    
                System.out.println(Arrays.toString(arry));
            }

### 希尔排序（Shell Sort）： ###

对于简单插入排序，存在一个效率的问题如2,3,4,5,1这个数组，使用插入排序他的顺序是

\{2 3 4 5 5\}  
\{2 3 4 4 5\}  
\{2 3 3 4 5\}  
\{2 2 3 4 5\}  
\{1 2 3 4 5\}  不难看出 我们只需要换一个数然后过程执行了五次，对效率有很大影响，此时我们可以引入一种改进后的插入排序，那就是希尔排序，也叫缩小增量排序。

希尔排序就是按照下标一定增量进行分组，每组再按照直接插入算法排序，随着组的减少，每组的元素也越来越少，当组数减少至为1时，整个文件分成1组，算法便终止。

演示：

![20190829162726552.gif][]

代码：

（交换法）

package sort;
    
    import java.util.Arrays;
    
    public class ShellSort {
        public static void main(String[] args) {
            int temp=0;
            int arry[]={3,2,1,6,5,7,8,4,9,0};
            // gap代表分了多少组
            for(int gap =arry.length/2;gap>0;gap/=2){
                //i代表第几组开始是 第0 6个 1 7个  2 8个 3 9个 4 10个为一组
                for (int i=gap;i<arry.length;i++){
                    //j代表第几组的第几个元素
                    for(int j=i-gap;j>=0;j-=gap){
                        if(arry[j]>arry[j+gap]){
                            temp=arry[j];
                            arry[j]=arry[j+gap];
                            arry[j+gap]=temp;
                        }
                    }
                }
                System.out.println(Arrays.toString(arry));
            }
    
        }
    }

（移步法）

int arry[]={3,2,1,6,5,7,8,4,9,0};
    
    
            // gap代表分了多少组
            for(int gap =arry.length/2;gap>0;gap/=2){
                //i代表第几组开始是 第0 6个 1 7个  2 8个 3 9个 4 10个为一组 共五个组那么0 和6肯定为一组
                for (int i=gap;i<arry.length;i++){
                int j=i;
                int temp=arry[j];
                if(arry[j]<arry[j-gap]){
                     while(j-gap>=0 && temp < arry[j - gap]){
                         arry[j]=arry[j-gap];
                         j-=gap;
                     }
                     arry[j]=temp;
                }
                }
                System.out.println(Arrays.toString(arry));
            }
        }

### 快速排序（Quick Sort）： ###

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。大致意思就是在一个数组中取中间元素比它小的方左边比它大的则放右边 两边元素再按照快排要求，最终变成有序序列。

演示：

![20190830144919541.gif][]

代码：

public static void quickSort(int[] arr, int left, int right) {
    		int l = left;// 左下标
    		int r = right;// 右下标
    		int pivot = arr[(left + right) / 2];// 找到中间的值
    		// 将比pivot小的值放在其左边，比pivot大的值放在其右边
    		while (l < r) {
    			// 在pivot左边寻找，直至找到大于等于pivot的值才退出
    			while (arr[l] < pivot) {
    				l += 1;// 将l右移一位
    			}
    			// 在pivot右边寻找，直至找到小于等于pivot的值才退出
    			while (arr[r] > pivot) {
    				r -= 1;// 将r左移一位
    			}
    			if (l >= r) {
    				// 左右下标重合，寻找完毕，退出循环
    				break;
    			}
    			// 交换元素
    			int temp = arr[l];
    			arr[l] = arr[r];
    			arr[r] = temp;
    
    			//倘若发现值相等的情况，则没有比较的必要，直接移动下标即可
    		
    			// 如果交换完后，发现arr[l]==pivot，此时应将r左移一位
    			if (arr[l] == pivot) {
    				r -= 1;
    			}
    			// 如果交换完后，发现arr[r]==pivot，此时应将l右移一位
    			if (arr[r] == pivot) {
    				l += 1;
    			}
    		}
    		// 如果l==r，要把这两个下标错开，否则会出现无限递归，导致栈溢出的情况
    		if (l == r) {
    			l += 1;
    			r -= 1;
    		}
    		// 向左递归
    		if (left < r) {
    			quickSort(arr, left, r);
    		}
    		// 向右递归
    		if (right > l) {
    			quickSort(arr, l, right);
    		}
    	}

### 归并排序（Merge Sort）： ###

## ##

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMTgzNDA5_size_16_color_FFFFFF_t_70][]

演示：

![20190830150307933.gif][]

代码：

public static void mergeSort(int[] arr, int left, int right, int[] temp) {
    		// 分解
    		if (left < right) {
    			int mid = (left + right) / 2;// 中间索引
    			// 向左递归进行分解
    			mergeSort(arr, left, mid, temp);
    			// 向右递归进行分解
    			mergeSort(arr, mid + 1, right, temp);// mid + 1，中间位置的后一个位置才是右边序列的开始位置
    			// 每分解一轮便合并一轮
    			merge(arr, left, right, mid, temp);
    		}
    	}
    
    	/**
    	 * 合并的方法
    	 * 
    	 * @param arr   待排序的数组
    	 * @param left  左边有序序列的初始索引
    	 * @param right 中间索引
    	 * @param mid   右边有序序列的初始索引
    	 * @param temp  做中转的数组
    	 */
    	public static void merge(int[] arr, int left, int right, int mid, int[] temp) {
    		int i = left; // 初始化i，左边有序序列的初始索引
    		int j = mid + 1;// 初始化j，右边有序序列的初始索引(右边有序序列的初始位置即为中间位置的后一个位置)
    		int t = 0;// 指向temp数组的当前索引，初始为0
    		// 先把左右两边的数据(已经有序)按规则填充到temp数组
    		// 直到左右两边的有序序列，有一边处理完成为止
    		while (i <= mid && j <= right) {
    			// 如果左边有序序列的当前元素小于或等于右边有序序列的当前元素，就将左边的元素填充到temp数组中
    			if (arr[i] <= arr[j]) {
    				temp[t] = arr[i];
    				t++;// 索引后移
    				i++;// i后移
    			} else {
    				// 反之，将右边有序序列的当前元素填充到temp数组中
    				temp[t] = arr[j];
    				t++;// 索引后移
    				j++;// j后移
    			}
    		}
    		// 把有剩余数据的一边的元素填充到temp中
    		while (i <= mid) {
    			// 此时说明左边序列还有剩余元素
    			// 全部填充到temp数组
    			temp[t] = arr[i];
    			t++;
    			i++;
    		}
    		while (j <= right) {
    			// 此时说明左边序列还有剩余元素
    			// 全部填充到temp数组
    			temp[t] = arr[j];
    			t++;
    			j++;
    		}
    		// 将temp数组的元素复制到原数组
    		t = 0;
    		int tempLeft = left;
    		while (tempLeft <= right) {
    			arr[tempLeft] = temp[t];
    			t++;
    			tempLeft++;
    		}
    	}

## ##

### 基数排序（radix sort）： ###

基数排序会分配是个桶 标号分别是0-9，在第一次排序时会将每个元素的个位取出，放到相应编号的桶中，然后按照桶的顺序依次放回原来的数组；进行第二次排序时，会将每个元素的十位取出放到相应编号的桶中，然后按照桶的顺序依次放回原来的数组；以此类推直到最高位排完，排序也就完成。

演示：

数组\{718，34，72，401，64\}进行基数排序

第一趟排序结果\{ 401 ，72 ，34 ， 64，718\}

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMTgzNDA5_size_16_color_FFFFFF_t_70 1][]

第二趟排序结果\{401，718，34，64，72\}

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMTgzNDA5_size_16_color_FFFFFF_t_70 2][]

第三趟排序结果\{34，64，72，401，718\}  排序完成 将元素返回原数组

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMTgzNDA5_size_16_color_FFFFFF_t_70 3][]

代码：

public static void raixSort(int[] arr) {
    		// 第一轮(针对每个元素的个位进行排序处理)
    
    		// 定义一个二维数组，模拟桶，每个桶就是一个一维数组
    		// 为了防止放入数据的时候桶溢出，我们应该尽量将桶的容量设置得大一些
    		int[][] bucket = new int[10][arr.length];
    		// 记录每个桶中实际存放的元素个数
    		// 定义一个一维数组来记录每个桶中每次放入的元素个数
    		int[] bucketElementCounts = new int[10];
    
    		for (int j = 0; j < arr.length; j++) {
    			// 取出每个元素的个位
    			int digitOfElement = arr[j] % 10;
    			// 将元素放入对应的桶中
    			// bucketElementCounts[digitOfElement]就是桶中的元素个数，初始为0，放在第一位
    			bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
    			// 将桶中的元素个数++
    			// 这样接下来的元素就可以排在前面的元素后面
    			bucketElementCounts[digitOfElement]++;
    		}
    		// 按照桶的顺序取出数据并放回原数组
    		int index = 0;
    		for (int k = 0; k < bucket.length; k++) {
    			// 如果桶中有数据，才取出放回原数组
    			if (bucketElementCounts[k] != 0) {
    				// 说明桶中有数据，对该桶进行遍历
    				for (int l = 0; l < bucketElementCounts[k]; l++) {
    					// 取出元素放回原数组
    					arr[index++] = bucket[k][l];
    				}
    			}
    			// 第一轮处理后，需要将每个bucketElementCounts[k]置0
    			bucketElementCounts[k] = 0;
    		}
    		System.out.println("第一轮:" + Arrays.toString(arr));
    
    		// ----------------------------
    
    		// 第二轮(针对每个元素的十位进行排序处理)
    		for (int j = 0; j < arr.length; j++) {
    			// 取出每个元素的十位
    			int digitOfElement = arr[j] / 10 % 10;
    			// 将元素放入对应的桶中
    			// bucketElementCounts[digitOfElement]就是桶中的元素个数，初始为0，放在第一位
    			bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
    			// 将桶中的元素个数++
    			// 这样接下来的元素就可以排在前面的元素后面
    			bucketElementCounts[digitOfElement]++;
    		}
    		// 按照桶的顺序取出数据并放回原数组
    		index = 0;
    		for (int k = 0; k < bucket.length; k++) {
    			// 如果桶中有数据，才取出放回原数组
    			if (bucketElementCounts[k] != 0) {
    				// 说明桶中有数据，对该桶进行遍历
    				for (int l = 0; l < bucketElementCounts[k]; l++) {
    					// 取出元素放回原数组
    					arr[index++] = bucket[k][l];
    				}
    			}
    			// 第二轮处理后，需要将每个bucketElementCounts[k]置0
    			bucketElementCounts[k] = 0;
    		}
    		System.out.println("第二轮:" + Arrays.toString(arr));
    
    		// ----------------------------
    
    		// 第三轮(针对每个元素的百位进行排序处理)
    		for (int j = 0; j < arr.length; j++) {
    			// 取出每个元素的百位
    			int digitOfElement = arr[j] / 100 % 10;
    			// 将元素放入对应的桶中
    			// bucketElementCounts[digitOfElement]就是桶中的元素个数，初始为0，放在第一位
    			bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
    			// 将桶中的元素个数++
    			// 这样接下来的元素就可以排在前面的元素后面
    			bucketElementCounts[digitOfElement]++;
    		}
    		// 按照桶的顺序取出数据并放回原数组
    		index = 0;
    		for (int k = 0; k < bucket.length; k++) {
    			// 如果桶中有数据，才取出放回原数组
    			if (bucketElementCounts[k] != 0) {
    				// 说明桶中有数据，对该桶进行遍历
    				for (int l = 0; l < bucketElementCounts[k]; l++) {
    					// 取出元素放回原数组
    					arr[index++] = bucket[k][l];
    				}
    			}
    			// 第三轮处理后，需要将每个bucketElementCounts[k]置0
    			bucketElementCounts[k] = 0;
    		}
    		System.out.println("第三轮:" + Arrays.toString(arr));
    	}

[20190828190943289.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/0d9b9f63efb644fd91d216c664eef0bf.gif
[Link 1]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0/715313
[20190829103956425.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/5260faccfbdc419cb7438f7d22aa480f.gif
[20190829160510706.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/f5aa5fdb8563492a86386abf0cac4235.gif
[20190829162726552.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/1e72ca9b3b7b43698853bf0d54cc6755.gif
[20190830144919541.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/b2fe513849be474ab3ca5c8b6b959256.gif
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMTgzNDA5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/2f195fd8158c40f3ac64893ad30917a7.png
[20190830150307933.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/c59e73462c5045888846ba9f69c6c334.gif
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMTgzNDA5_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/faba8c6dec474bacbaa9c7558b03eeea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMTgzNDA5_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/d9ce2f214654488c8760bd9709cbc7f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMTgzNDA5_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/a6e353b5cd674573a92035d211efc977.png