快速排序相关(学习笔记)

快速排序相关(学习笔记)

1)快排的原理是什么?快速写一段核心代码实现。

A.快速排序的原理解释

首先,在符合递归条件下进行

其次,得到基准元素位置

①从数列中取出第一个数作为基准元素

②实现元素的移动(比基准元素大的放右边,小于或等于放左边)

方法一:挖坑填数,选定基准元素Pivot,并记住位置index(坑位),并且设置两个指针right和left,在上面的分区过程中,符合条件能够左右置换的,被比较的数将坑位填满,自己成为下一个坑位,继续比较下去,直到right和left重合在了同一位置,再将Pivot元素放置到index,并得到基准元素位置。

方法二:指针交换法,控制指针、进行比较、判断是否需要移动、交换指针指向的元素,right和left重合,Pivot元素替换,得到基准元素位置。

最后,再对左右区间进行递归。

B.快速写一段核心代码实现:

public static void quickSort(int[] arr, int right, int left) {
         if (right >= left || arr == null || arr.length <= 1) {
             return;
        }
         int i = right, j = end, pivot = arr[(right + left) / 2];
         while (i <= j) {
             while (arr[i] < pivot) {
                 ++i;
             }
             while (arr[j] > pivot) {
                 --j;
             }
             if (i < j) {
                 int t = arr[i];
                 arr[i] = arr[j];
                 arr[j] = t;
                 ++i;
                 --j;
            } else if (i == j) {
                 ++i;
             }
         }
        quickSort(arr, right, j);
        quickSort(arr, i, left);
    }
}

2) DualPivotQuicksort的sort代码实现int排序的原理和关键步骤

因为数列的特征不同,利用快速排序时基准元素的选择会直接影到响最终的效果。经过对数组具体情况的多重考量和细分,得出先对int[]数组进行测试,再选择合适的排序方法,才能真正的提高效率。

DualPivotQuicksort的sort代码实现int排序的原理和关键步骤:

1. 判断数组int[] a的长度是否大于常量286(QUICKSORT_THRESHOLD)

若right-left <QUICKSORT_THRESHOLD,小数组使用快速排序

2.判断数组int[]a的长度是否大于常量47(INSERTION_SORT_THRESHOLD)

若right-left < INSERTION_SORT_THRESHOLD,使用插入排序。

3.判断该数组int[]a是否已经高度结构化(即已经接近排序完成):

检查数组是不是已经接近有序状态:a.否(有序数列的个数超过了MAX_RUN_COUNT),使用快速排序;b.是,判断该数组是否已经排列好,没有的话使用归并排序。

4.在上述情况都不满足的情况下,使用双基准快速排序算法进行排序。

思路和上面快速排序差不多,不同的是要选取两个Pivot(P1、P2)和部分算法的优化处理。

系统通过位运算int seventh = (length >> 3) + (length >> 6) + 1;获取数组长度的1/7的近似值;之后获取本数组中间位置的索引e3(int e3 = (left + right) >>> 1; // The midpoint);在中间位置的左右1/7, 2/7处各获取两个索引(e2, e1, e4, e5);再获取四个索引,将这五个索引对应的值用插入算法进行排序, 再放回五个索引的位置;对索引值进行排序,判断五个索引对应的元素值是否相同,不相同时,使e2的值作为Pivot1, e4的值作为Pivot2,进行双基准快速排序,相同时选取e3的值作为Pivot,进行单基准快速排序。