189 lines
5.1 KiB
Markdown
189 lines
5.1 KiB
Markdown
## 每日一题 - 重复数据排序优化
|
||
|
||
### 信息卡片
|
||
|
||
- 时间：2019-06-11
|
||
- tag：`Quike Sort`
|
||
|
||
### 题目描述
|
||
|
||
```
|
||
如果一个数组含有大量重复元素，我们应该选择什么样的排序方法，背后的理论依据是什么”？
|
||
```
|
||
|
||
|
||
### 参考答案
|
||
|
||
取决于数据分布如何
|
||
|
||
1. 如果数据的总类很少, 而且每个都有大量重复的元素, 那么使用计数排序, 那么这个时间复杂度能够达到O(N).
|
||
```java
|
||
public class CountSort {
|
||
public int[] countSort(int[] array) {
|
||
int max = array[0];
|
||
for(int i=1; i<array.length; i++) {
|
||
if(array[i]>max) {
|
||
max = array[i];
|
||
}
|
||
}
|
||
//创建计数数组
|
||
int[] countArray = new int[max+1];
|
||
for(int i=0; i<array.length; i++) {
|
||
countArray[array[i]]++;
|
||
}
|
||
int index = 0;
|
||
//创建返回数组
|
||
int[] sortArray = new int[array.length];
|
||
for(int i=0; i<countArray.length; i++) {
|
||
for(int j=0; j<countArray[i]; j++) {
|
||
sortArray[index++] = i;
|
||
}
|
||
}
|
||
return sortArray;
|
||
}
|
||
}
|
||
```
|
||
2. 如果数据没有明显的规律, 可以考虑快排. 其性能与pivot的选择有关. 如果每次partition过程中的pivot选择能够较好的平分数组, 那么快排的速度能够达到O(NlogN). 因此再选择pivot时候, 可以选择数组中几个中间大小的数字. 此外, 对于重复数量大的数据, 可以选择三路快排来排序. 最后, 因为再数据近乎有序的时候, 插入排序的速度可以达到O(N), 所以在数据近乎有序的时候, 我们使用插入排序来优化排序过程.
|
||
|
||
```java
|
||
private class QuickSort{
|
||
|
||
// 快排转化成为插入排序的阈值
|
||
private static final int INSERTION_SORT_THRESHOLD = 47;
|
||
|
||
public void QuickSort(int[] a) {
|
||
if (a.length > 0) {
|
||
quickSort(a, 0, a.length - 1);
|
||
}
|
||
}
|
||
|
||
private void swap(int[] arr, int a, int b) {
|
||
int temp = arr[a];
|
||
arr[a] = arr[b];
|
||
arr[b] = temp;
|
||
}
|
||
|
||
private int choosePivotMedianOfThree(int[] a, int l, int r) {
|
||
int mid = 0;
|
||
if ((r-l+1) % 2 == 0) {
|
||
mid = l + (r-l+1)/2 - 1;
|
||
} else {
|
||
mid = l + (r-l+1)/2;
|
||
}
|
||
|
||
// 只需要找出中位数即可，不需要交换
|
||
if (((a[l]-a[mid]) * (a[l]-a[r])) <= 0) {
|
||
return l;
|
||
} else if (((a[mid]-a[l]) * (a[mid]-a[r])) <= 0) {
|
||
return mid;
|
||
} else {
|
||
return r;
|
||
}
|
||
}
|
||
|
||
private void quickSort(int[] a, int left, int right) {
|
||
if (right <= left)
|
||
return;
|
||
|
||
// 在数据近乎有序的时候, 插入排序的性能近乎于O(N)
|
||
if(right - left <= INSERTION_SORT_THRESHOLD) {
|
||
insertSort(a, left, right)
|
||
}
|
||
|
||
/*
|
||
* 工作指针
|
||
* p指向序列左边等于pivot元素的位置
|
||
* q指向序列右边等于Pivot元素的位置
|
||
* i指向从左向右扫面时的元素
|
||
* j指向从右向左扫描时的元素
|
||
*/
|
||
int p, q, i, j;
|
||
int pivot;// 锚点
|
||
i = p = left;
|
||
j = q = right - 1;
|
||
|
||
|
||
/*
|
||
* 每次总是取序列最右边/最优和最中间的元素的大小中间值为锚点
|
||
*/
|
||
pivot = choosePivotMedianOfThree(a, left, right);
|
||
|
||
//始终将第一个元素作为pivot, 若不是, 则与之交换
|
||
if (pivot != left) {
|
||
swap(a, pivot, left);
|
||
}
|
||
pivot = a[right];
|
||
|
||
while (true) {
|
||
/*
|
||
* 工作指针i从右向左不断扫描，找小于或者等于锚点元素的元素
|
||
*/
|
||
while (i < right && a[i] <= pivot) {
|
||
/*
|
||
* 找到与锚点元素相等的元素将其交换到p所指示的位置
|
||
*/
|
||
if (a[i] == pivot) {
|
||
swap(a, i, p);
|
||
p++;
|
||
}
|
||
i++;
|
||
}
|
||
/*
|
||
* 工作指针j从左向右不断扫描，找大于或者等于锚点元素的元素
|
||
*/
|
||
while (left <= j && a[j] >= pivot) {
|
||
/*
|
||
* 找到与锚点元素相等的元素将其交换到q所指示的位置
|
||
*/
|
||
if (a[j] == pivot) {
|
||
swap(a, j, q);
|
||
q--;
|
||
}
|
||
j--;
|
||
}
|
||
/*
|
||
* 如果两个工作指针i j相遇则一趟遍历结束
|
||
*/
|
||
if (i >= j)
|
||
break;
|
||
|
||
/*
|
||
* 将左边大于pivot的元素与右边小于pivot元素进行交换
|
||
*/
|
||
swap(a, i, j);
|
||
i++;
|
||
j--;
|
||
}
|
||
/*
|
||
* 因为工作指针i指向的是当前需要处理元素的下一个元素
|
||
* 故而需要退回到当前元素的实际位置，然后将等于pivot元素交换到序列中间
|
||
*/
|
||
i--;
|
||
p--;
|
||
while (p >= left) {
|
||
swap(a, i, p);
|
||
i--;
|
||
p--;
|
||
}
|
||
/*
|
||
* 因为工作指针j指向的是当前需要处理元素的上一个元素
|
||
* 故而需要退回到当前元素的实际位置，然后将等于pivot元素交换到序列中间
|
||
*/
|
||
j++;
|
||
q++;
|
||
while (q <= right) {
|
||
swap(a, j, q);
|
||
j++;
|
||
q++;
|
||
}
|
||
|
||
/*
|
||
* 递归遍历左右子序列
|
||
*/
|
||
quickSort(a, left, i);
|
||
quickSort(a, j, right);
|
||
}
|
||
}
|
||
```
|
||
|