自己整理的六大排序笔记 (希望对你有帮助)：插入排序、堆排序、归并排序、计数排序、快速排序(单轴快排，双轴快排)、冒泡排序

清疚 2022-08-28 03:50 113阅读 0赞

### 排序方法 ###

*  //1.冒泡排序 (Bubble Sort)
 *   *   *  简介
         *  算法描述
         *  时间复杂度
         *  代码模板
 *  //2.插入排序 (Insertion Sort)
 *   *   *  简介
         *  步骤
         *  优化插入
         *  优化插入位置的查找
 *  //3.堆排序 (Heapsort)
 *   *   *  简介
         *  步骤
         *  时间复杂度
         *  代码
 *  //4.归并排序 (Merge Sort)
 *   *   *  简介
         *  算法描述
         *  时间复杂度
         *  空间复杂度
         *  代码
 *  //5.计数排序 (Counting Sort)
 *   *   *  简介
         *  算法描述
         *  时间复杂度
 *  //6.快速排序 (Quick Sort)
 *   *   *  简介
         *  算法描述(赋值填充方式)
         *  时间复杂度
         *  空间复杂度
         *  代码
         *  优化
     *  //6.1.单轴快排 (Single Pivot Quick Sort)
     *   *   *  简介
             *  步骤
             *  划分方式
         *  //6.1.2.优化：三分单向扫描
         *   *   *  作用
                 *  步骤
         *  //6.1.3.优化：三分双向扫描
         *   *   *  作用
     *  //6.2.双轴快排 (Dual Pivot Quick Sort)
     *   *   *  简介
             *  步骤

# //1.冒泡排序 (Bubble Sort) #

### 简介 ###

*  冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端

### 算法描述 ###

*  1：比较相邻的元素。如果第一个比第二个大，就交换它们两个
 *  2：对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
 *  3：针对所有的元素重复以上的步骤，除了最后一个
 *  4：重复步骤1~3，直到排序完成

### 时间复杂度 ###

*  最佳情况：T(n) = O(n)
 *  最差情况：T(n) = O(n2)
 *  平均情况：T(n) = O(n2)

### 代码模板 ###

// 数组为空，则不进行冒泡排序
    if (arr == null || arr.length == 0) {
        
    	return;
    }
    
    // 轮次，每轮会将最大的数移至最右
    for (int i = 0; i < array.length; i++) {
        
    	// 一轮元素的交换次数，即最左边的元素逐个与右边的元素比较的次数
        for (int j = 0; j < array.length - 1 - i; j++) {
        
        	// 判断是否交换，即左边的元素比右边大
            if (array[j] > array[j + 1]) {
        
           		// 进行交换
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

--------------------

# //2.插入排序 (Insertion Sort) #

### 简介 ###

*  顾名思义，采用插入的方式，对无序数列进行排序。
 *  维护一个有序区，将数据一个一个插入到有序区的适当位置，直到整个数组都有序。

### 步骤 ###

*  (1)：先把首元素作为有序区，此时有序区只有一个元素。
 *  (2)：将下一个元素和有序区的所有元素从右向左比较(找到位置插入)。大于等于比较的元素时，则不需要交换。小于比较的元素时，则进行交换，再向左比较，直到不需要交换。
 *  (3)：直到整个数列的元素插入完毕。

### 优化插入 ###

*  用于减少无谓的交换。
 *  和有序区的所有元素比较。大于等于时，则不用插入。小于比较的元素时，复制比较的元素到它自己的右边(之前待插入的位置)，直到遇见大于等于比较的元素。将待插入元素，插入到比较的元素的右边(待插入的位置)。

### 优化插入位置的查找 ###

*  可以使用二分查找来找到待插入位置，然后再进行插入操作。

--------------------

# //3.堆排序 (Heapsort) #

### 简介 ###

*  堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父结点。

### 步骤 ###

*  1：初始化数组，创建大顶堆、大顶堆的创建从下往上比较，不能直接用无序数组从根节点比较，否则有的不符合大顶堆的定义
 *  2：交换根节点和倒数第一个数据，现在倒数第一个数据就是最大的
 *  3：重新建立大顶堆、因为只有 array\[0\] 改变，其它都符合大顶堆的定义，所以可以根节点 array\[0\] 重新建立
 *  4：重复2、3的步骤，直到只剩根节点 array\[0\]，即 i=1。

### 时间复杂度 ###

*  最佳情况：T(n) = O(nlogn)
 *  最差情况：T(n) = O(nlogn)
 *  平均情况：T(n) = O(nlogn)

### 代码 ###

// 开始排序
    public static void heapSort(int[] arr) {
        
    	// 数组为空，则不进行堆排序
        if (arr == null || arr.length == 0) {
        
            return;
        }
    	
    	// 保存数组长度
        int len = arr.length;
        // 构建大顶堆，这里其实就是把待排序序列，变成一个大顶堆结构的数组
        buildMaxHeap(arr, len);
    
        // 交换堆顶和当前末尾的节点，重置大顶堆
        for (int i = len - 1; i > 0; i--) {
        
            swap(arr, 0, i);
            len--;
            heapify(arr, 0, len);
        }
    }
    
    // 构建大顶堆的方法
    private static void buildMaxHeap(int[] arr, int len) {
        
        // 从最后一个非叶节点开始向前遍历，调整节点性质，使之成为大顶堆
        for (int i = (int)Math.floor(len / 2) - 1; i >= 0; i--) {
        
            heapify(arr, i, len);
        }
    }
    
    // 调整节点的方法
    private static void heapify(int[] arr, int i, int len) {
        
        // 先根据堆性质，找出它左右节点的索引
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // 默认当前节点（父节点）是最大值。
        int largestIndex = i;
        if (left < len && arr[left] > arr[largestIndex]) {
        
            // 如果有左节点，并且左节点的值更大，更新最大值的索引
            largestIndex = left;
        }
        if (right < len && arr[right] > arr[largestIndex]) {
        
            // 如果有右节点，并且右节点的值更大，更新最大值的索引
            largestIndex = right;
        }
    
        if (largestIndex != i) {
        
            // 如果最大值不是当前非叶子节点的值，那么就把当前节点和最大值的子节点值互换
            swap(arr, i, largestIndex);
            // 因为互换之后，子节点的值变了，如果该子节点也有自己的子节点，仍需要再次调整。
            heapify(arr, largestIndex, len);
        }
    }
    
    // 交换两个元素的位置方法
    private static void swap (int[] arr, int i, int j) {
        
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

--------------------

# //4.归并排序 (Merge Sort) #

### 简介 ###

*  归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并

### 算法描述 ###

*  把长度为n的输入序列分成两个长度为n/2的子序列
 *  对这两个子序列分别采用归并排序
 *  将两个排序好的子序列合并成一个最终的排序序列

### 时间复杂度 ###

*  最佳情况：T(n) = O(nlogn)
 *  最差情况：T(n) = O(nlogn)
 *  平均情况：T(n) = O(nlogn)

### 空间复杂度 ###

*  O(n)

### 代码 ###

// 分隔序列的方法
    public static int[] MergeSort(int[] array) {
        
        // 传入数组的元素小于两个，则直接返回
        if (array.length < 2) return array;
    
        // 保存数组的中间位置
        int mid = array.length / 2;
        // 将数组分成两个长度为 n / 2 的子序列
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
    
        // 对这两个子序列分别采用分隔序列的方法，再进行归并
        return merge(MergeSort(left), MergeSort(right));
    }
    
    // 归并方法
    public static int[] merge(int[] left, int[] right) {
        
        // 保存归并后的数组，长度为两个数组的总和
        int[] result = new int[left.length + right.length];
    
        // 开始归并
        // index 为 result 数组中归并到的元素索引
        // i 为 left 数组中遍历到的索引
        // j 为 right 数组中遍历到的索引
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
        
            if (i >= left.length)
                // left 数组已添加完，则添加 right 中遍历到的元素
                result[index] = right[j++];
            else if (j >= right.length)
                // right 数组已添加完，则添加 left 中遍历到的元素
                result[index] = left[i++];
            // 都没添加完，则比较两个数组中，遍历到的元素
            else if (left[i] > right[j])
                // right 中的元素更小，则添加该元素
                result[index] = right[j++];
            else
                // left 中的元素更小，则添加该元素
                result[index] = left[i++];
        }
        return result;
    }

--------------------

# //5.计数排序 (Counting Sort) #

### 简介 ###

*  计数排序是一个非基于比较的排序算法。优势在于在对一定范围内的整数排序时，它的复杂度为 O(n + k) (其中k是整数的范围)，快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法，而且当 O(k) > O(n \* log\*(n)) 时其效率反而还不如基于比较的排序

### 算法描述 ###

*  用一个数组来存一些数的出现次数 (数组下标代表存数的值，值代表次数)

### 时间复杂度 ###

*  O(n + k)

--------------------

# //6.快速排序 (Quick Sort) #

### 简介 ###

*  快速排序是指通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序(递归)，以达到整个序列有序
 *  因为跳跃性的数据交换，导致算法实际上不能保证原先的两个相等的元素的顺序，所以快速排序是不稳定的排序算法。

### 算法描述(赋值填充方式) ###

*  从数列中挑出一个元素，称为 “基准”，无论这个基数的位置在哪儿，拿出来之后就形成一个坑
 *  然后遍历从右侧开始，寻找比基数更小的数，挖出来（留出一个坑），填到原先的坑里；然后从左侧寻找比基数大的数，填到上一步的坑里；这就是主体逻辑
 *  重新排序完数列后，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作；
 *  递归地让小于基准值元素的子数列和大于基准值元素的子数列再度调用快速排序算法。

### 时间复杂度 ###

*  最佳情况：T(n) = O(n)
 *  最差情况：T(n) = O(nlogn)
 *  平均情况：T(n) = O(nlogn)

### 空间复杂度 ###

*  最佳情况：O(logn)
 *  最差情况：O(n)
 *  平均情况：O(logn)

### 代码 ###

public static int[] QuickSort(int[] array, int start, int end) {
        
    	if (array.length < 1 || start < 0 || end >= array.length || start > end) return null;
    	int smallIndex = partition(array, start, end);
    	if (smallIndex > start)
    		QuickSort(array, start, smallIndex - 1);
    	if (smallIndex < end)
    		QuickSort(array, smallIndex + 1, end);
    	return array;
    }
    public static int partition(int[] array, int start, int end) {
        
    	int pivot = (int) (start + Math.random() * (end - start + 1));
    	int smallIndex = start - 1;
    	swap(array, pivot, end);
    	for (int i = start; i <= end; i++)
    		if (array[i] <= array[end]) {
        
    			smallIndex++;
    			if (i > smallIndex)
    				swap(array, i, smallIndex);
    		}
    	return smallIndex;
    }
    public static void swap(int[] array, int i, int j) {
        
    	int temp = array[i];
    	array[i] = array[j];
    	array[j] = temp;
    }

### 优化 ###

*  三点中值法：优化主元的选取  
    取数组左边界元素、中间元素以及右边界元素，进行比较，取三者的中值定为主元。
 *  绝对中值法：优化主元的选取  
    取数组中真正的中值作为主元。
 *  待排序列较短时，直接用插入排序：优化排序  
    在数组长度小于或等于8时，插入排序更快。

--------------------

## //6.1.单轴快排 (Single Pivot Quick Sort) ##

#### 简介 ####

*  是快速排序最简单的实现。
 *  顾名思义，单轴，就是要利用一个"轴"(pivot)完成排序。

#### 步骤 ####

*  (1)：如果待排序的数组项数为 0 或 1，直接返回。(递归出口)
 *  (2)：在待排序的数组中任选一个元素，作为中心点(pivot)。
 *  (3)：将小于 pivot 的元素放在前面，大于 pivot 的元素放在后面。
 *  (4)：对前面小于 pivot 的元素和大于 pivot 的元素分别进行快速排序。

#### 划分方式 ####

*  元素划分方式：用指针 i 和 j，在两端扫描交换的方式。i 与 j 相遇后就停止比较，将相遇点所在的元素和中心点(pivot)交换。
 *  赋值填充方式：用指针 i 和 j，一边挖坑一边填充的方式。一开始在 pivot 挖坑，j 找到比 pivot 小的值后，将这个值填到上一个坑，i 找到比 pivot 大的值后，填到上一个坑。i 与 j 相遇后就停止比较，将 pivot 填到相遇的点。
 *  单向扫描划分方式：用指针 i 和 j，单向扫描划分的方式。初始时，i = start，j = start + 1，j负责扫描整个序列。j扫描到比 pivot 小的值时，i++，并将i元素与j元素交换，然后 j 扫描下一个。遇到大于或等于 pivot 的值时，直接扫描下一个。扫描完整个序列后，可得 start+1 ~ i 是小于 pivot 的，i+1 ~ j 是大于等于 pivot 的。将 pivot 和 i(小于pivot的最后一个)进行交换。

### //6.1.2.优化：三分单向扫描 ###

##### 作用 #####

*  对于序列 \[2，2，2，2，3，1\]，会发现这种大量元素等于 pivot 的序列，单轴快排并没有起到很好的划分作用。如果将等于 pivot 的元素也作为一个划分区段，则可以将序列划分为3段：小于 pivot 的元素，等于 pivot 的元素，大于 pivot 的元素。

##### 步骤 #####

*  (1)：初始化时，i = start，j = end，k = start + 1，k负责扫描。
 *  (2)：k 扫描到比 pivot 小的值时， i 与 k 元素交换，i++，然后 k 扫描下一个。遇到大于 pivot 的元素时，k 与 j 元素交换，j–，然后 k 再次扫描当前位置的元素。遇到等于 pivot 的元素时，直接扫描下一个。
 *  (3)：pivot已在等于pivot的分段中，无需交换。直到 k > j 时停止扫描。
 *  (4)：扫描完整个序列后，可得 start ~ i-1 是小于 pivot 的，i ~ k-1 是等于 pivot 的，j+1 ~ end 是大于 pivot 的。

### //6.1.3.优化：三分双向扫描 ###

##### 作用 #####

*  三分单项扫描中，扫描到大于 pivot 的元素，将最后一个未扫描的元素(j所在的元素)与当前元素(k所在的元素)进行交换。那如果这个扫描的元素正好是比 pivot 大的元素呢，这无疑增加了交换的次数。
 *  所以 j 索引应当扫描到一个不比 pivot 大的元素，再做判断。如果元素小于 pivot，则 j 与 k 交换，再让 k 与 i 交换，i++。如果元素等于 pivot，则直接让 j 与 k 交换。如果直到 k > j 都没有找到，则代表后面的待排序元素全部大于 pivot，直接结束排序。如果没有结束排序，k继续扫描下一个。

--------------------

## //6.2.双轴快排 (Dual Pivot Quick Sort) ##

#### 简介 ####

*  顾名思义，取两个中心点 pivot1，pivot2，且 pivot <= pivot2，可将序列分成三段，然后分别对三段进行递归。
 *  三段分别是：小于 pivot1 的元素，在 pivot1 和 pivot2 中间的元素，大于 pivot2 的元素。

#### 步骤 ####

*  (1)：如果待排序的数组项数为 0 或 1，直接返回。(递归出口)
 *  (2)：初始化时，pivot1=arr\[start\]，pivot2=arr\[end\]。然后 i = start，j = end，k = start + 1，k负责扫描。
 *  (3)：k 扫描到比 pivot1 小的值时， i+1 后与 k 元素交换，然后 k 扫描下一个。遇到大于 pivot2 的元素时，j 向左扫描到一个不比 pivot2 大的元素。如果小于 pivot1，则 j 与 k 交换，然后 i+1 再与 k 交换。如果在 pivot1 和 pivot2 中间，则直接让 j 与 k 交换。如果直到 k > j 都没有找到，则直接结束排序。如果没有结束排序，k 继续扫描下一个。遇到在 pivot1 和 pivot2 中间的元素时，直接扫描下一个。
 *  (4)：扫描完整个序列后，将 pivot1 与 i 交换，pivot2 与 j 交换，可得 start ~ i-1 是小于 pivot1 的，i+1 ~ j-1 是在 pivot1 和 pivot2 中间的，j+1 ~ end 是大于 pivot2 的。
 *  (5)：对前面分完的三段再次调用快速排序方法。