前些日子,java网友聊排序,
谈到Java库的排序算法有双轴快排比普通快排好,
然后一个好奇,就度娘看了看原理思想,自己写着练手
说下算法核心大概思想:
QuickSort:
取一个基数,把元素划分2边,
一边小于这个基数,一边大于这个基数,
然后一直这样划分到最小,也就把所有元素排序完成了
dualPivotQuickSort:
核心思想跟上面一样,都是划分元素
不过这个有2个基数,也就是把元素划分3份
接下来直接分享学习源码:
C++版:经典快排
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
//交换2个元素void QuickSort::swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp;}/** * 快速排序的核心算法 * @param arr 需要排序的数组 * @param start 排序的开始位置 * @param end 排序的结束位置 */ void QuickSort::qSort(int* arr, int start, int end) { //防止无限递归 if (end > start) { int low = start++; int high = end; int pivot = arr[low]; //基于pivot划分位置 while (start < end) { if (arr[start] < pivot) { start++; } else { this->swap(arr+start, arr+end--); } } //防止停止位置的值大于基数 if (arr[start] >= pivot) { start--; } this->swap(arr+start, arr+low); //继续划分更小 this->qSort(arr, low, start); this->qSort(arr, start + 1, high); }} |
C++版:双轴快排
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
/** * 双轴快速排序的核心算法 * @param arr 需要排序的数组 * @param start 排序的开始位置 * @param end 排序的结束位置 */void QuickSort::dualPivotQuickSort(int* arr, int start, int end) { //如果数量太少则直接采用经典的单轴快排 if (end - start < 64) { this->qSort(arr, start, end); return; } //双轴快排核心 int low = start++; int high = end--; //先排序前面6个元素 this->qSort(arr, low, low + 5); //初始化双轴的2个基数 this->swap(arr+low, arr+low + 1); this->swap(arr+high, arr+low + 3); int pivotLow = arr[low], pivotHigh = arr[high]; int lowIndex = low + 1, highIndex = high - 1; //基于pivot划分位置 while (start < end) { //小于左边基数 if (arr[start] < pivotLow) { this->swap(arr+start++, arr+lowIndex++); } //大于右边基数 else if (arr[start] > pivotHigh) { this->swap(arr+start, arr+highIndex--); end--; } //位置2个基数中间 else { start++; } } //修正基数位置 --lowIndex; if (arr[highIndex] < pivotLow) { this->swap(arr+low, arr+highIndex); } else if (arr[highIndex] >= pivotHigh) { --highIndex; } //继续划分更小 dualPivotQuickSort(arr, low, lowIndex);//左边 dualPivotQuickSort(arr, lowIndex + 1, highIndex);//中间 dualPivotQuickSort(arr, highIndex + 1, high);//右边} |
C++版:双轴快速无递归方式
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
/** * 双轴快速排序的核心算法_去掉递归 * @param arr 需要排序的数组 * @param start 排序的开始位置 * @param end 排序的结束位置 */void QuickSort::dualPivotQuickSortNoRecursion(int* arr, int start, int end) { int indexLen = pow(log2(end - start), 2) + 8; int current = indexLen; int* index = new int[indexLen+1];SORT: //如果数量太少则直接采用经典的单轴快排 if (end - start < 64) { this->qSort(arr, start, end); //判断是否全部排序完成 if (current < indexLen){ start = index[++current]; end = index[++current]; goto SORT; } else { return; } } //双轴快排核心 int low = start++; int high = end--; //先排序前面6个元素 this->qSort(arr, low, low + 5); //初始化双轴的2个基数 this->swap(arr + low, arr + low + 1); this->swap(arr + high, arr + low + 3); int pivotLow = arr[low], pivotHigh = arr[high]; int lowIndex = low + 1, highIndex = high - 1; //基于pivot划分位置 while (start < end) { //小于左边基数 if (arr[start] < pivotLow) { this->swap(arr + start++, arr + lowIndex++); } //大于右边基数 else if (arr[start] > pivotHigh) { this->swap(arr + start, arr + highIndex--); end--; } //位置2个基数中间 else { start++; } } //修正基数位置 --lowIndex; if (arr[highIndex] < pivotLow) { this->swap(arr + low, arr + highIndex); } else if (arr[highIndex] >= pivotHigh) { --highIndex; } //分割位置_最大 index[current--] = high; index[current--] = highIndex + 1; //分割位置_中间 index[current--] = highIndex; index[current--] = lowIndex + 1; //分割位置_最小 end = lowIndex; start = low; goto SORT;} |
其实,这些东西,我真心用不上
只是刚好网友聊到,自己失业没事做,陪着他玩了,
感觉这些知道下概念就行,真写都用别人封装好的
java的也写了一份,一起分享了吧
java版:经典快排
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
/** * 快速排序的核心算法 * @param arr 需要排序的数组 * @param start 排序的开始位置 * @param end 排序的结束位置 */ public void qSort(int[] arr,int start,int end){ //防止无限递归 if(end>start){ int low =start++; int high = end; int pivot =arr[low]; //基于pivot划分位置 while (start < end){ if (arr[start] < pivot){ start++; }else { swap(arr,start,end--); } } //防止停止位置的值大于基数 if (arr[start] >= pivot){ start--; } swap(arr,start,low); //继续划分更小 qSort(arr,low,start); qSort(arr,start+1,high); } } /** * 交换数组中的2个元素 * @param arr 数组 * @param indexA 元素A的位置 * @param indexB 元素B的位置 */ public void swap(int[] arr,int indexA,int indexB){ int temp = arr[indexA]; arr[indexA] = arr[indexB]; arr[indexB]=temp; } |
java版:双轴快排
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
/** * 快速排序 * @param arr 需要排序的数组 */ public void quickSort(int[] arr){ dualPivotQuickSort(arr,0,arr.length-1); } /** * 双轴快速排序的核心算法 * @param arr 需要排序的数组 * @param start 排序的开始位置 * @param end 排序的结束位置 */ public void dualPivotQuickSort(int[] arr,int start,int end){ //如果数量太少则直接采用经典的单轴快排 if (end-start < 64) { qSort(arr,start,end); return; } //双轴快排核心 int low =start++; int high = end--; //先排序前面6个元素 qSort(arr,low,low+5); //初始化双轴的2个基数 swap(arr,low,low+1); swap(arr,high,low+3); int pivotLow =arr[low],pivotHigh =arr[high]; int lowIndex =low+1,highIndex=high-1; //基于pivot划分位置 while (start < end){ //小于左边基数 if (arr[start] < pivotLow){ swap(arr,start++,lowIndex++); } //大于右边基数 else if(arr[start] > pivotHigh){ swap(arr,start,highIndex--); end--; } //位置2个基数中间 else{ start++; } } //修正基数位置 --lowIndex; if (arr[highIndex] < pivotLow ) { swap(arr,low,highIndex); }else if (arr[highIndex] >= pivotHigh){ --highIndex; } //继续划分更小 dualPivotQuickSort(arr,low,lowIndex);//左边 dualPivotQuickSort(arr,lowIndex+1,highIndex);//中间 dualPivotQuickSort(arr,highIndex+1,high);//右边 } |
