常用排序算法对比分析及java代码实现

朴灿烈づ我的快乐病毒、 2023-01-22 14:57 2阅读 0赞

# 常用排序算法对比分析及java代码实现 #

## 1.复杂度对比 ##

<table> 
 <tbody> 
  <tr> 
   <td colspan="7">常用排序算法</td> 
  </tr> 
  <tr> 
   <td>排序类别</td> 
   <td>排序方法</td> 
   <td colspan="3">时间复杂度</td> 
   <td>空间复杂度</td> 
   <td>稳定性</td> 
  </tr> 
  <tr> 
   <td>平均情况</td> 
   <td>最好情况</td> 
   <td>最坏情况</td> 
   <td>辅助存储</td> 
  </tr> 
  <tr> 
   <td>插入排序</td> 
   <td>直接插入排序</td> 
   <td>O(n^2)</td> 
   <td>O(n)</td> 
   <td>O(n^2)</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td>O(nlogn)~O(n^2)</td> 
   <td>O(n^1.3)</td> 
   <td>O(n^2)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>选择排序</td> 
   <td>选择排序</td> 
   <td>O(n^2)</td> 
   <td>O(n^2)</td> 
   <td>O(n^2)</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>交换排序</td> 
   <td>冒泡排序</td> 
   <td>O(n^2)</td> 
   <td>O(n)</td> 
   <td>O(n2)</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(n^2)</td> 
   <td>O(nlogn)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td colspan="2">归并排序</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(n)</td> 
   <td>稳定</td> 
  </tr> 
 </tbody> 
</table>

## 2.详解 ##

### 2.1 直接插入排序 ###

#### 2.1.1 原理 ####

每次将未排序的数字按照大小插入到前面已排序数组的合适位置中。

#### 2.1.2 图解 ####

![直接插入排序算法原理][20210630203524993.png]

#### 2.1.3 Java代码实现 ####

import java.util.Arrays;
    
    public class InsertSort { 
        public static void main(String[] args) { 
            int[] array = { 49, 38, 65, 97, 76, 13, 27, 49, 10};
            insertSort(array);
        }
    
        /** * 直接插入排序步骤： * 1.取未排序的数组中的第一个值（第一层for） * 2.将未排序数组中取出的值去已排序的数组中比较，插入相应位置（第二层for） * @param arr 待排序数组 */
        private static void insertSort(int[] arr) { 
            //如果数组为空或者只有一个值
            if (arr == null && arr.length == 1) { 
                return ;
            }
            //如果数组的长度大于等于2
            for (int i = 1; i < arr.length; i++) { 
                int temp = arr[i];//用来缓存需要移动的数值
                boolean flag = false;//标志是否插入成功
                for (int j = i - 1; j >= 0; j--) { 
                    if (temp < arr[j]) { 
                        arr[j + 1] = arr[j];
                        System.out.println(Arrays.toString(arr));
                    } else { 
                        arr[j + 1] = temp;
                        flag = true;
                        break;
                    }
                }
                if (!flag) { 
                    arr[0] = temp;
                }
            }
        }
    }

#### 2.1.4 直接插入排序缺点 ####

不难发现，每次都是从有序数组的最后一位开始，向前扫描的，这意味着，如果当前值比有序数组的第一位还要小，那就必须比较有序数组的长度n次。

#### 2.1.5 直接插入排序的优化 ####

我们可以在排序过程中插入哨兵位来记录上一次插入的位置，如果此次插入的值比哨兵位上的值小，则只需要比较哨兵位左侧的值即可，反之同理。

#### 2.1.6 优化代码实现 ####

// 根据上一次的位置，简化下一次定位
         private static void insertSortOptimization(int[] array) { 
             if (array == null || array.length < 2) { 
                 return;
             }
             // 记录上一个插入值的位置和数值
             int checkN = array[0];
             int checkI = 0;
             // 循环插入
             for (int i = 1; i < array.length; i++) { 
                 int cur = array[i];
                 int start = i - 1;
                 // 根据上一个值，定位开始遍历的位置
                 if (cur < checkN) { 
                     start = checkI;
                     for (int j = i - 1; j > start - 1; j--) { 
                         array[j + 1] = array[j];
                     }
                 }
                 // 剩余情况是：checkI 位置的数字，和其下一个坐标位置是相同的
                 // 循环判断+插入
                 boolean flag = false;
                 for (int j = start; j >= 0; j--) { 
                     if (cur < array[j]) { 
                         array[j + 1] = array[j];
                     } else { 
                         array[j + 1] = cur;
                         checkN = cur;
                         checkI = j + 1;
                         flag = true;
                         break;
                     }
                 }
                 if (!flag) { 
                     array[0] = cur;
                 }
             }
         }

### 2.2 希尔排序 ###

#### 2.2.1 原理 ####

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。希尔排序时直接插入排序的一种优化算法。

#### 2.2.2 图解 ####

![在这里插入图片描述][20210712200607892.gif]

#### 2.2.3 Java代码实现 ####

/** * 希尔排序步骤： * 1.先确定分组间隔（第一层for） * 2.确定数组的左侧和右侧角标（第二三层for） * 3.对左侧和右侧角标对应的值进行比较，并交换 * @param arr 待排序数组 * @return 返回排序好的数组 */
       private static int[] shellSort(int[] arr) { 
           if (arr == null || arr.length <= 1) { 
               return arr;
           }
           //希尔排序 升序
           for (int d = arr.length / 2; d > 0; d /= 2) {  //d：增量 7 3 1
               for (int i = d; i < arr.length; i++) { 
                   //i:代表即将插入的元素角标，作为每一组比较数据的最后一个元素角标
                   //j:代表与i同一组的数组元素角标
                   for (int j = i - d; j >= 0; j -= d) {  //在此处-d 为了避免下面数组角标越界
                       if (arr[j] > arr[j + d]) { // j+d 代表即将插入的元素所在的角标
                           //符合条件，插入元素（交换位置）
                           int temp = arr[j];
                           arr[j] = arr[j + d];
                           arr[j + d] = temp;
                       }
                   }
               }
           }
           return arr;
       }

### 2.3 选择排序 ###

#### 2.3.1 原理 ####

（1）从待排序序列中，找到关键字最小的元素；  
（2）如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；  
（3）从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。

#### 2.3.2 图解 ####

![在这里插入图片描述][20210712204117355.gif]

#### 2.3.3 Java代码实现 ####

import java.util.Arrays;
    
    public class SelectSort { 
        public static void main(String[] args) { 
            int[] array = { 49, 38, 65, 97, 76, 13, 27, 49, 10};
            selectSort(array);
            System.out.println(Arrays.toString(array));
        }
    
        /** * 简单选择排序步骤： * 1.依次遍历序列当中的每一个元素（第一层for） * 2.将遍历得到的当前元素依次与余下的元素进行比较，符合最小元素的条件，则交换。（第二层for） * * @param arr 待排序数组 */
        private static void selectSort(int[] arr) { 
            for (int i = 0; i < arr.length - 1 - i; i++) { 
                int min = i;
                int max = arr.length - 1 - i;
                // 每轮需要比较的次数 N-i
                for (int j = i + 1; j < arr.length - i; j++) { 
                    if (arr[j] < arr[min]) { 
                        // 记录目前能找到的最小值元素的下标
                        min = j;
                    }
                    if (arr[j] > arr[max]) { 
                        //记录目前能找到的最大值元素的下标
                        max = j;
                    }
                }
                // 将找到的最小值和i位置所在的值进行交换
                if (i != min) { 
                    int tmp = arr[i];
                    arr[i] = arr[min];
                    arr[min] = tmp;
                }
                if (arr.length - 1 - i != max) { 
                    int tmp = arr[arr.length - 1 - i];
                    arr[arr.length - 1 - i] = arr[max];
                    arr[max] = tmp;
                }
            }
        }
    }

#### 2.3.4 选择排序缺点 ####

选择排序每次都要从未排序的数组中遍历取最小值，非常浪费时间。

#### 2.3.5 选择排序的优化 ####

可以在选择排序的过程中，在记录最小值的同时记录最大值，可以极大降低检索时间。

#### 2.3.6 优化代码实现 ####

private static int[] selectSortOptimization(int[] arr) { 
            for (int i = 0; i < arr.length - 1 - i; i++) { 
                int min = i;
                int max = arr.length - 1 - i;
                // 每轮需要比较的次数 N-i
                for (int j = i + 1; j < arr.length  - i; j++) { 
                    if (arr[j] < arr[min]) { 
                        // 记录目前能找到的最小值元素的下标
                        min = j;
                    }
                    if (arr[j] > arr[max]) { 
                        //记录目前能找到的最大值元素的下标
                        max = j;
                    }
                }
                // 将找到的最小值和i位置所在的值进行交换
                if (i != min) { 
                    int tmp = arr[i];
                    arr[i] = arr[min];
                    arr[min] = tmp;
                }
                if (arr.length - 1 - i != max) { 
                    int tmp = arr[arr.length - 1 - i];
                    arr[arr.length - 1 - i] = arr[max];
                    arr[max] = tmp;
                }
            }
            return arr;
        }

### 2.4 堆排序 ###

#### 2.4.1 原理 ####

（1）构建一个大根堆；  
（2）将堆顶取出，与数组中的最后一个值互换；  
（3）对剩余元素重复执行1-2步操作，直到排序完成。

#### 2.4.2 图解 ####

![堆排序][20210713194527812.gif]

#### 2.4.3 Java代码实现 ####

import java.util.Arrays;
    
    public class HeapSort { 
        public static void main(String[] args) { 
            int[] array = { 49, 38, 65, 97, 76, 13, 27, 49, 10};
            heapSort(array);
            System.out.println(Arrays.toString(array));
        }
    
        /** * 堆排序步骤： * 1.首先构建全局大根堆 * （1）构建全局大根堆之前需要构建局部大根堆 * 2.取得大根堆的根节点，然后将根节点与大根堆最后一个值做交换 * 3.再对未排序序列进行1-2步骤操作，直到整棵树排序完毕 * * @param arr 待排序数组 */
        private static void heapSort(int[] arr) { 
            build_heap(arr);
            for (int i = arr.length - 1; i > 0; i--) { 
                swap(arr, 0, i);
                heapify(arr, 0, i);
            }
        }
    
        /** * 构建全局大根堆 * 要保证全局大根堆，只要保证非叶子节点为大根堆即可 * * @param arr 待排序数组 */
        private static void build_heap(int[] arr) { 
            int last = arr.length - 1;
            int parent = (last - 1) / 2;//parent为非叶子节点的最大下标
            for (int i = parent; i >= 0; i--) { 
                heapify(arr, i, arr.length);
            }
        }
    
        /** * 对数组的一个分支进行大根堆构建,构建局部大根堆 * * @param arr 待排序数组 * @param parent 待排序父节点 * @param length 待排序数组长度 */
        private static void heapify(int[] arr, int parent, int length) { 
            int max = parent;//假设父节点的值最大
            int left = 2 * parent + 1;//树的左孩子节点下标
            int right = 2 * parent + 2;//树的右孩子节点下标
            if (parent > length) { 
                return;
            }
            //寻找父节点，左孩子节点，右孩子节点的最大值的下标
            if (left < length && arr[left] > arr[max]) { 
                max = left;
            }
            if (right < length && arr[right] > arr[max]) { 
                max = right;
            }
            if (max != parent) { 
                //交换最大值为根节点
                swap(arr, max, parent);
                //已交换的孩子节点再构建大根堆
                heapify(arr, max, length);
            }
        }
    
        /** * 交换数组中的两个值的位置 * * @param arr 待交换数组 * @param value1 待交换的值1的下标 * @param value2 待交换的值2的下标 */
        private static void swap(int[] arr, int value1, int value2) { 
            int temp = arr[value1];
            arr[value1] = arr[value2];
            arr[value2] = temp;
        }
    }

#### 2.4.4 堆排序的优缺点 ####

**优点：**  
（1）堆排序的效率与快排、归并相同，都达到了基于比较的排序算法效率的峰值；  
（2）除了高效之外，最大的亮点就是只需要O(1)的辅助空间了，既最高效率又最节省空间，只此一家了  
堆排序效率相对稳定，无论待排序序列是否有序，堆排序的效率都是O(nlogn)不变；  
**缺点：**（从上面看，堆排序几乎是完美的，那么为什么最常用的内部排序算法是快排而不是堆排序呢？）  
最大的也是唯一的缺点就是——堆的维护问题，实际场景中的数据是频繁发生变动的，而对于待排序序列的每次更新（增，删，改），我们都要重新做一遍堆的维护，以保证其特性，这在大多数情况下都是没有必要的。（所以快排成为了实际应用中的老大，而堆排序只能在算法书里面顶着光环，当然这么说有些过分了，当数据更新不很频繁的时候，当然堆排序更好些）

### 2.5 冒泡排序 ###

#### 2.5.1 原理 ####

（1）从左至右依次比较相邻的两个值，如果左侧的值比右侧的值大，则交换两个值的位置；  
（2）第一次排序结束后，能取出序列中最大的值；  
（3）对剩余元素重复执行1-2步操作，直到排序完成。

#### 2.5.2 图解 ####

![冒泡排序][20210714190226835.gif]

#### 2.5.3 java代码实现 ####

import java.util.Arrays;
    
    public class BubbleSort { 
        public static void main(String[] args) { 
            int[] array = { 49, 38, 65, 97, 76, 13, 27, 49, 10};
            bubbleSort(array);
            System.out.println(Arrays.toString(array));
        }
    
        /** * 冒泡排序步骤： * 1.遍历待排序数组，取出数组中最大值（第二层for） * 2.取出剩余待排序数组中的最大值，一直到数组遍历结束(第一层for) * * @param arr 待排序数组 */
        private static void bubbleSort(int[] arr) { 
            for (int i = arr.length - 1; i > 0; i--) { 
                for (int j = 0; j < i; j++) { 
                    if (arr[j] > arr[j + 1]) { 
                        swap(arr, j, j + 1);
                    }
                }
            }
        }
    
        /** * 交换两个位置的值 * * @param arr 待交换数组 * @param value1 待交换下标1 * @param value2 待交换下标2 */
        private static void swap(int[] arr, int value1, int value2) { 
            int temp = arr[value1];
            arr[value1] = arr[value2];
            arr[value2] = temp;
        }
    }

### 2.6 快速排序 ###

#### 2.6.1 原理 ####

快排可以简单理解为找基准数据在数组中的位置，直到找到所有基准数组的位置。快排的主要思想为分治法。  
（1）对于一个待排序数组，先选定一个基准数据；  
（2）对整个数组进行排序，小于基准数组的数字放在左边，大于基准数组的数字放在右边；  
（3）以基准数组分割，左侧作为子数组1重复1-2步操作，右侧作为子数组2重复1-2步骤；  
（4）直到全部排序完成。

#### 2.6.2 图解 ####

![快速排序][20210714193337158.gif]

#### 2.6.3 java代码实现 ####

import java.util.Arrays;
    
    public class QuickSort { 
        public static void main(String[] args) { 
            int[] array = { 49, 38, 65, 97, 76, 13, 27, 49, 10};
            quickSort(array, 0, array.length - 1);
            System.out.println(Arrays.toString(array));
        }
    
        /** * 快速排序步骤： * 快速排序可以简单理解为找基准数据在数组中的位置 * 1.对待排序数组找基准数据的索引值 * 2.对索引值左右两侧数据重复1步骤 */
        private static void quickSort(int[] arr, int low, int high) { 
            if (low < high) { 
                int index = getIndex(arr, low, high);
                quickSort(arr, low, index - 1);//对基准值左侧排序
                quickSort(arr, index + 1, high);//对基准值右侧排序
            }
        }
    
        private static int getIndex(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;//填补最后一个位置数据，这里的low可以为high，因为最终low=high
            return low;//返回基准值下标
        }
    }

#### 2.6.4 快速排序优化 ####

（1）随机取基准数字；  
（2）三数取中法；  
（3）三数取中+插排；  
（4）三数取中+插排+聚集相等元素；  
（5）三数取中+插排+聚集相等元素+尾递归；  
（6）STL中的Sort函数。  
这里效率最好的是方法（5），效率和（6）差不多。  
详细内容可参考：[快速排序的5种优化方法][5].

### 2.7 归并排序 ###

#### 2.7.1 原理 ####

归并排序是采用分治法的一个典型的应用。  
（1）首先将所有元素拆分为最小单元序列；  
（2）将最小单元序列两两合并，在合并时保证合并之后的序列有序；  
（3）一直到所有序列合并为一个序列为止，数组排序完成。

#### 2.7.2 图解 ####

![在这里插入图片描述][20210714195607427.gif]

#### 2.7.3 java代码实现 ####

import java.util.Arrays;
    
    public class MergeSort { 
        public static void main(String[] args) { 
            int[] array = { 49, 38, 65, 97, 76, 13, 27, 49, 10};
            int[] tempArr = new int[array.length];
            mergeSort(array, 0, array.length - 1, tempArr);
            System.out.println(Arrays.toString(array));
        }
    
        /** * 归并排序步骤： * 1.对两个已经排好序的数组进行合并：merge方法 * 2.对全局数据递归拆分合并：mergeSort方法 * * @param arr 待排序数组 * @param low 数组的头下标 * @param high 数组的尾下标 * @param tempArr 缓存数组 */
        private static void mergeSort(int[] arr, int low, int high, int[] tempArr) { 
            int mid = (low + high) / 2;
            if (low < high) { 
                mergeSort(arr, low, mid, tempArr);
                mergeSort(arr, mid + 1, high, tempArr);
                merge(arr, low, mid, high, tempArr);
            }
        }
    
        private static void merge(int[] arr, int low, int mid, int high, int[] tempArr) { 
            int i = 0;//tempArr的初始下标
            int j = low;//左侧数组开始位置下标
            int k = mid + 1;//右侧数组开始位置
            while (j <= mid && k <= high) { 
                //比较左右两侧数组的第一个值，谁小就把谁放进缓存数组中
                if (arr[j] < arr[k]) { 
                    tempArr[i++] = arr[j++];
                } else { 
                    tempArr[i++] = arr[k++];
                }
            }
            //当比较完两个数组的值之后，将剩下数组还有的值全部放进缓存数组中
            while (j <= mid) { 
                tempArr[i++] = arr[j++];
            }
            while (k <= high) { 
                tempArr[i++] = arr[k++];
            }
            for (int t = 0; t < i; t++) { //把缓存数组中的值全部放进原数组
                arr[low + t] = tempArr[t];
            }
        }
    }

#### 2.7.4 归并排序优化 ####

（1）归并排序的递归在处理小规模问题时会使方法调用过于频繁，可以使用插入排序处理小规模的排序；  
（2）如果序列已经有序，那么后面的合并就没必要执行，当a\[mid\] <= a\[mid+1\]时，跳过merge方法；  
详细内容可参考：[归并排序及其优化][Link 1].

## 3.参考 ##

[数据结构常见的八大排序算法][Link 2].  
[数据结构的那些排序算法总是记不住，这个真的背的吗？][Link 3].  
[快速排序的5种优化方法][5].

[20210630203524993.png]: /images/20221020/f5c86a69911542de8abc5b943371f213.png
[20210712200607892.gif]: /images/20221020/09483de7659b4176b857a74fed1eec42.png
[20210712204117355.gif]: /images/20221020/c01bd5b86fc7469a981a6a53ef5e7a6f.png
[20210713194527812.gif]: /images/20221020/e31a37281f704fcbb9fb664529fec30b.png
[20210714190226835.gif]: /images/20221020/a4fbe93b0a24466386aaceb927d46a5b.png
[20210714193337158.gif]: /images/20221020/268ea64aabff41a4aa502a6c6e1a198b.png
[5]: https://blog.csdn.net/qq_19525389/article/details/81436838
[20210714195607427.gif]: /images/20221020/71c8d87e586540b9bf817bcae4cee1e7.png
[Link 1]: https://www.jianshu.com/p/356368ccd32d
[Link 2]: https://www.cnblogs.com/hokky/p/8529042.html
[Link 3]: https://www.zhihu.com/question/51337272