七大排序算法总结

• 经总结，排序算法大体可以分为以下七大种（含核心思想）：
  1. 冒泡排序：通过相邻元素的比较和交换来将最大（或最小）的元素逐渐“冒泡”到数组的一端
  2. 选择排序：在未排序部分的数据中选择最小（或最大）的元素，然后将其放置到已排序部分的末尾
  3. 插入排序：将待排序的元素逐个插入到已排序部分的正确位置
  4. 归并排序：采用分治法，将已有序的子序列合并，得到完全有序的序列；
  5. 快速排序： 通过选取基准元素，将数组划分为两个子数组，并对子数组递归排序，实现整个数组的快速排序
  6. 希尔排序：通过较大间隔的插入排序来使数组中的元素局部有序，从而减少后续插入排序的工作量
  7. 堆排序：将待排序的元素构建成一个最大堆（大顶堆或最小堆），然后将堆顶元素与堆的最后一个元素交换，然后重新调整堆，使得剩余的元素仍然构成一个最大堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

1.冒泡排序

1. 核心思想： 通过相邻元素的比较和交换来将最大（或最小）的元素逐渐“冒泡”到数组的一端

   

2. 具体步骤：

   1. 从数组的第一个元素开始，依次比较相邻的两个元素。
   2. 如果前一个元素大于后一个元素，则交换它们的位置，使得较大的元素“冒泡”到后面。
   3. 继续进行相邻元素的比较和交换，直到数组的末尾。
   4. 重复执行上述步骤，每次都会将当前未排序部分的最大元素“冒泡”到数组的末尾。
   5. 重复执行上述步骤，直到整个数组排序完成。

3. 实现代码：

   public static void bubbleSort(int[] arr) {
         
       int temp = 0;
       for (int i = arr.length - 1; i > 0; i--) {
          	// 每次需要排序的长度
           for (int j = 0; j < i; j++) {
          			// 从第一个元素到第i个元素
               if (arr[j] > arr[j + 1]) {
         			// 确保较大的元素排到后面
                   temp = arr[j];
                   arr[j] = arr[j + 1];
                   arr[j + 1] = temp;
               }
           }
       }
   }
   

4. 时间和空间复杂度：

   • 平均情况：O(n2)
   • 最好情况：O(n)
   • 最坏情况：O(n2)
   • 空间复杂度：O(1)
   • 稳定性：稳定

5. 优化： 增加标记符swap，用于确定当前一轮冒泡是否有元素进行交换，若没有则跳出循环，表示数组已经有序了

   public static void bubbleSort(int[] arr) {
         
       int temp = 0;
       boolean swap;
       for (int i = arr.length - 1; i > 0; i--) {
          // 每次需要排序的长度
           swap=false;
           for (int j = 0; j < i; j++) {
          // 从第一个元素到第i个元素
               if (arr[j] > arr[j + 1]) {
         
                   temp = arr[j];
                   arr[j] = arr[j + 1];
                   arr[j + 1] = temp;
                   swap=true;
               }
           }//loop j
           if (swap==false){
         			//前面的一轮循环没有进行交换，数组已经有序
               break;
           }
       }//loop i
   }// method bubbleSort
   

2.选择排序

1. 核心思想： 在未排序部分的数据中选择最小（或最大）的元素，然后将其放置到已排序部分的末尾

2. 具体步骤：

   1. 遍历数组，将第一个元素作为当前最小（或最大）元素。
   2. 在未排序部分的剩余元素中，找到最小（或最大）的元素，并记录其位置。
   3. 将找到的最小（或最大）元素与未排序部分的第一个元素交换位置，将其放置到已排序部分的末尾。
   4. 重复执行上述步骤，每次都会将当前未排序部分的最小（或最大）元素放置到已排序部分的末尾。
   5. 这样，经过n-1轮的遍历和交换，整个数组就会按照升序（或降序）排列。

3. 实现代码：

   public static void selectionSort(int[] arr) {
         
       int temp, min = 0;
       for (int i = 0; i < arr.length - 1; i++) {
         
           min = i;
           // 循环查找最小值
           for (int j = i + 1; j < arr.length; j++) {
         
               if (arr[min] > arr[j]) {
         
                   min = j;
               }
           }
           if (min != i) {
         
               temp = arr[i];
               arr[i] = arr[min];
               arr[min] = temp;
           }
       }
   }
   

4. 时间和空间复杂度：

   • 平均情况：O(n2)
   • 最好情况：O(n2)
   • 最坏情况：O(n2)
   • 空间复杂度：O(1)
   • 稳定性：不稳定

5. 关于稳定性的探讨：

   • 稳定性：在排序过程中，相等元素的相对顺序是否会被改变。如果排序算法能够保持相等元素的相对顺序不变，则称其为稳定的排序算法；反之，则称其为不稳定的排序算法

   • 冒泡排序（升序）：当相邻元素进行比较并需要交换位置时，只有当后面的元素小于前面的元素才会进行交换。因此，对于相等的元素，即使它们相邻，它们的相对顺序也不会被改变，从而保持了排序的稳定性

   • 选择排序：每次选择最小的元素并放置到已排序部分的末尾。在寻找最小（或最大）元素的过程中，可能会导致相等元素的相对顺序发生改变。例如，在一组相等的元素中，由于选择排序每次只选择一个最小（或最大）元素，所以在选择的过程中可能会交换这些相等元素的位置，从而导致排序的不稳定性

   • 举例：假设我们有以下一组待排序的元素：

     [5①, 2, 7, 5②, 1]
     

     • 冒泡排序：比较相邻的元素，并根据需要交换它们的位置。当遇到相等元素时，只有在后面的元素小于前面的元素时才会进行交换。

       第一轮冒泡排序：[2, 5①, 5②, 1, 7]
       第二轮冒泡排序：[2, 5, 1, 5, 7]
       第三轮冒泡排序：[2, 1, 5, 5, 7]
       第四轮冒泡排序：[1, 2, 5, 5, 7]
       

     • 选择排序：

       第一轮选择排序：[1, 2, 7, 5②, 5①]（选择1） （两个相等的5的位置发生变化，不稳定!!!）
       第二轮选择排序：[1, 2, 5, 5, 7]（选择2）
       第三轮选择排序：[1, 2, 5, 5, 7]（选择5）
       第四轮选择排序：[1, 2, 5, 5, 7]（选择5）
       第五轮选择排序：[1, 2, 5, 5, 7]（选择7）
       

3.插入排序

1. 核心思想： 将待排序的元素逐个插入到已排序部分的正确位置

   

2. 具体步骤：

   1. 将数组分为已排序部分和未排序部分。一开始，已排序部分只包含第一个元素，即数组的第一个元素被认为是已排序的。
   2. 从未排序部分取出一个元素，将其插入到已排序部分的正确位置。为了找到正确的位置，可以从已排序部分的末尾开始，依次向前比较已排序元素，直到找到小于等于该元素的位置。
   3. 将该元素插入到找到的位置，并将已排序部分中的元素向后移动，为新元素腾出位置。
   4. 重复步骤2和步骤3，直到未排序部分为空。
   5. 最终，已排序部分即为排序好的数组。

3. 实现代码：

   public static void insertionSort(int[] arr) {
         
       int n = arr.length;
       for (int i = 1; i < n; i++) {
         		//从第二个元素开始，第一个元素默认有序
       	int key = arr[i];				//保存当前元素 key
           int j = i - 1;
   		
           //找到合适的位置
           while (j >= 0 && arr[j] > key) {
         //发现已排序元素比 key 大，则将该元素向后移动一位，直到找到 key 的正确位置
           	arr[j + 1] = arr[j];
   			j = j - 1;					//往后移
           }	
           arr[j + 1] = key;1				//找到 key 保存的位置
      	}
   }
   

   待排序数组：[5, 2, 4, 6, 1, 3]
   1：[2, 5, 4, 6, 1, 3]
   2：[2, 4, 5, 6, 1, 3]
   3：[1, 2, 4, 5, 6, 3]
   4：[1, 2, 3, 4, 5, 6]
   

4. 时间和空间复杂度：

   • 平均情况：O(n2)
   • 最好情况：O(n)
   • 最坏情况：O(n2)
   • 空间复杂度：O(1)
   • 稳定性：稳定

4.二分插入排序

1. 核心思想：利用二分查找来确定待插入元素在已排序部分中的位置，以减少比较次数

2. 实现步骤：

   1. 初始状态：将数组的第一个元素视为已排序部分，其余元素视为待排序部分。
   2. 插入过程：从第二个元素开始遍历待排序部分，对于每个元素，使用二分查找确定其在已排序部分中的插入位置。
   3. 二分查找：在已排序部分中，使用二分查找找到第一个大于待插入元素的位置，这个位置及之后的元素都需要向后移动一个位置来腾出空间。
   4. 插入操作：将待插入元素插入到找到的位置，完成一轮插入操作。
   5. 重复步骤2~4，直到待排序部分中的所有元素都被插入到已排序部分中，整个数组就被排序完成了。

3. 实现代码：

   public static void binaryInsertionSort(int[] arr) {
         
       int n = arr.length;
       for (int i = 1; i < n; i++) {
         
           int key = arr[i];
           int left = 0;
           int right = i - 1;
   
           // 二分查找确定插入位置
           int insertIndex = binarySearch(arr, left, right, key);
   
           // 将大于 key 的元素向后移动一位
           for (int j = i - 1; j >= insertIndex; j--) {
         
               arr[j + 1] = arr[j];
           }
   
           // 插入 key
           arr[insertIndex] = key;
       }
   }
   
   // 二分查找
   private static int binarySearch(int[] arr, int left, int right, int key) {
         
       while (left <= right) {
         
           int mid = left + (right - left) / 2;
           if (arr[mid] == key) {
         
               return mid; // key 在已排序部分的位置
           } else if (arr[mid] < key) {
         
               left = mid + 1;
           } else {
         
               right = mid - 1;
           }
       }
       return left; // 返回待插入位置
   }
   

4. 时间和空间复杂度：

   • 平均情况：O(n2)
   • 最好情况：O(n)
   • 最坏情况：O(n2)
   • 空间复杂度：O(1)
   • 稳定性：稳定

5.归并排序

1. 核心思想： 采用分治法，将已有序的子序列合并，得到完全有序的序列；

2. 步骤：

   1. 分解（Divide）：将原始数组分解为较小的子数组，直到每个子数组只有一个元素为止。这可以通过递归的方式实现，将数组不断二分直到每个子数组的长度为1。
   2. 解决（Conquer）：对每个子数组进行排序。对于只有一个元素的子数组来说，可以认为它们已经是有序的。
   3. 合并（Merge）：合并相邻的子数组，形成一个更大的有序数组。合并过程中，需要按照大小顺序逐个比较两个子数组中的元素，并将较小（或较大）的元素依次放入一个临时数组中，直到合并完成。
   4. 递归合并（Recursively Merge）：重复以上步骤，直到所有子数组都被合并成一个大的有序数组为止。

   

3. 实现代码：

   public static void mergeSort(int[] arr){
         
       int[] temp =new int[arr.length];
       internalMergeSort(arr, temp, 0, arr.length-1);
   }
   private static void internalMergeSort(int[] arr, int[] temp, int left, int right){
         
       //当left==right的时，已经不需要再划分了
       if (left<right){
         
           int middle = (left+right)/2;
           internalMergeSort(arr, temp, left, middle);          //左子数组
           internalMergeSort(arr, temp, middle+1, right);       //右子数组
           mergeSortedArray(arr, temp, left, middle, right);    //合并两个子数组
       }
   }
   // 合并两个有序子序列
   private static void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){
         
       int i=left;      
       int j=middle+1;
       int k=0;
       while (i<=middle && j<=right){
         
           temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
       }
       while (i <=middle){
         
           temp[k++] = arr[i++];
       }
       while ( j<=right){
         
           temp[k++] = arr[j++];
       }
       //把数据复制回原数组
       for (i=0; i<k; ++i){
         
           arr[left+i] = temp[i];
       }
   }
   

4. 时间和空间复杂度：

   • 平均情况：O(nlogn)
   • 最好情况：O(nlogn)
   • 最坏情况：O(nlogn)
   • 空间复杂度：O(n)
   • 稳定性：稳定

5. 适用场景： 归并排序在数据量比较大的时候也有较为出色的表现（效率上），但是，其空间复杂度O(n)使得在数据量特别大的时候（例如，1千万数据）几乎不可接受。而且，考虑到有的机器内存本身就比较小，因此，采用归并排序一定要注意。

6.快速排序

1. 核心思想： 通过选取基准元素，将数组划分为两个子数组，并对子数组递归排序，实现整个数组的快速排序

2. 实现步骤：

   1. 从数列中挑出一个元素，称为 “基准”（pivot），
   2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
   3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

3. 实现代码：

   public static void quickSort(int[] arr){
         
       qsort(arr, 0, arr.length-1);
   }
   
   private static void qsort(int[] arr, int low, int high){
         
       if (low >= high)
           return;
       int pivot = partition(arr, low, high);        //将数组分为两部分
       qsort(arr, low, pivot-1);                   //递归排序左子数组
       qsort(arr, pivot+1, high);                  //递归排序右子数组
   }
   
   private static int partition(int[] arr, int low, int high){
         
       int pivot = arr[low];     //基准
       while (low < high){
         
           
           while (low < high && arr[high] >= pivot){
         
               --high;
           } 
           
           arr[low]=arr[high];             //比基准小的元素会被移动到基准的左边
           
           while (low < high && arr[low] <= pivot){
         
               ++low;
           }
           
           arr[high] = arr[low];           //比基准大的元素会被移动到基准的右边
       }
       //扫描完成，基准到位
       arr[low] = pivot;
       //返回的是基准的位置
       return low;
   }
   

4. 举例：

   初始：[7, 2, 1, 6, 8, 5, 3, 4]	# 7为基准
   	 
   第一：[4, 2, 1, 6, 8, 5, 3, 4] # 4移到左边
   	 [4, 2, 1, 6, 8, 5, 3, 8] # 8移到右边
   	 [4, 2, 1, 6, 3, 5, 3, 8] # 3移到左边
   	 [4, 2, 1, 6, 3, 5, 7, 8] # 基准7插入到low位置
   	 
   划分为两个数组：[4, 2, 1, 6, 3, 5]和[8]
   第二： [4, 2, 1, 6, 3, 5] # 以4为基准
   	  [3, 2, 1, 6, 3, 5] # 3移到左边
   	  [3, 2, 1, 6, 6, 5] # 6移到右边
   	  [3, 2, 1, 4, 6, 5] # 基准4插入到low位置
   	 
   以此类推......
   

5. 时间和空间复杂度：

   • 平均情况：O(nlogn)
   • 最好情况：O(nlogn)
   • 最坏情况：O(n2)
   • 空间复杂度：O(logn)~O(n)
   • 稳定性：不稳定

7.希尔排序

1. 核心思想： 通过较大间隔的插入排序来使数组中的元素局部有序，从而减少后续插入排序的工作量

2. 实现步骤：

   • 选择增量序列：希尔排序的关键是选择增量序列，即确定每次分割子序列的间隔。通常选择的增量序列是经过优化的，以达到更好的排序效果。常见的增量序列有希尔增量序列（1, 4, 13, 40…）、Hibbard增量序列（1, 3, 7, 15…）等。
   • 对子序列进行插入排序：根据选择的增量序列，将待排序数组分割成若干个子序列，对每个子序列进行插入排序。插入排序会使得每个子序列局部有序。
   • 逐步缩小增量：重复以上步骤，逐步缩小增量，直到增量为1。当增量为1时，整个数组变为一个序列，此时进行最后一次插入排序即可完成排序。

3. 实现代码：

   public class ShellSort {
         
       public static void shellSort(int[] arr) {
         
           int n = arr.length;
           
           // 初始化增量，这里使用希尔增量序列
           int gap = 1;
           while (gap < n / 3) {
         
               gap = gap * 3 + 1;
           }
           
           // 增量逐步缩小至1
           while (gap > 0) {
         
               // 对每个子序列进行插入排序
               for (int i = gap; i < n; i++) {
         
                   int temp = arr[i];
                   int j = i;
                   // 对当前子序列进行插入排序
                   while (j >= gap && arr[j - gap] > temp) {
         
                       arr[j] = arr[j - gap];
                       j -= gap;
                   }
                   arr[j] = temp;
               }
               // 缩小增量
               gap = gap / 3;
           }
       }
   
       public static void main(String[] args) {
         
           int[] arr = {
         12, 34, 54, 2, 3};
           shellSort(arr);
           System.out.println("排序后的数组：");
           for (int num : arr) {
         
               System.out.print(num + " ");
           }
       }
   }
   

4. 时间和空间复杂度：

   • 平均情况：O(nlogn)—O(n2)
   • 最好情况：O(1.3n)
   • 最坏情况：O(n2)
   • 空间复杂度：O(1)
   • 稳定性：不稳定

8.堆排序（重要）

8.1堆概念

1. 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
2. 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

8.2核心思想、实现步骤

1. 核心思想：将待排序的元素构建成一个最大堆（大顶堆或最小堆），然后将堆顶元素与堆的最后一个元素交换，然后重新调整堆，使得剩余的元素仍然构成一个最大堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
2. 实现步骤：
   1. 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
   2. 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
   3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

8.3举例

1. 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

   • 假设给定无序序列结构如下：

     

   • 此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

     

   • 找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

     

   • 这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6

     

   • 此时，我们就将一个无需序列构造成了一个大顶堆。

2. 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

   • 将堆顶元素9和末尾元素4进行交换：

     

   • 重新调整结构，使其继续满足堆定义：

     

   • 再将堆顶元素8与末尾元素5进行交换，得到第二大元素8：

     

3. 后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

   

8.4代码举例

import java.util.Arrays;
public class Main{
    
    public static void main(String[] args) {
    
        int[] arr = new int[]{
    4,6,8,5,9};
        int length = arr.length;
        //从最后一个非叶节点开始构建大顶堆
        for (int i = arr.length/2-1; i >=0; i--) {
    
            maximumHeap(i,arr,length);
        }
        //从最小的叶子节点开始与根节点进行交换并重新构建大顶堆
        for (int i = arr.length-1; i >=0; i--) {
    
//            System.out.println(Arrays.toString(arr));
            swap(arr,0,i);
            length--;
            maximumHeap(0,arr,length);
        }
        System.out.println(Arrays.toString(arr));
    }
    //构建大顶堆
    public static void maximumHeap(int i,int[] arr,int length){
    
        int temp = arr[i];
        for (int j = i*2+1; j < length; j=j*2+1) {
    
            //如果右孩子大于做孩子，则指向右孩子
            if(j+1<length && arr[j+1]>arr[j]){
    
                j++;
            }
            //如果最大的孩子大于当前节点，则将大孩子赋给当前节点，修改当前节点为其大孩子节点，再向下走。
            if(arr[j]>temp){
    
                arr[i] = arr[j];
                i = j;
            }else{
    
                break;
            }
        }
        //将temp放到最终位置
        arr[i] = temp;
    }
    //交换
    public static void swap(int[] arr,int i,int j){
    
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

8.5时间空间复杂度

1. 时间复杂度： 堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为nlogn。所以堆排序时间复杂度最好和最坏情况下都是**O(nlogn)**级。

2. 空间复杂度：堆排序不要任何辅助数组，只需要一个辅助变量，所占空间是常数与n无关，所以空间复杂度为O(1)。

9.总结

排序	排序方法	平均情况	最好情况	最坏情况	空间	稳定性
1	冒泡排序	O(n2)	O(n)	O(n2)	O(1)	稳定
2	选择排序	O(n2)	O(n2)	O(n2)	O(1)	不稳定
3	插入排序	O(n2)	O(n)	O(n2)	O(1)	稳定
4	二分插入排序	O(n2)	O(n)	O(n2)	O(1)	稳定
5	归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
6	快速排序	O(nlogn)	O(nlogn)	O(n2)	O(logn)~O(n)	不稳定
7	希尔排序	O(nlogn) ~ O(n2)	O(n1.3)	O(n2)	O(1)	不稳定
8	堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定