赞
踩
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
快速排序的实现有以下几种实现方式:
//升序 //快速排序 void QuickSort(int* arr, int left, int right) { //递归终止条件 if (left >= right) { return; } int begin = left, end = right; //先排一趟 int key = left; while (left < right) { //右面的值比key对应的值大 while (left < right && arr[right] >= arr[key]) { --right; } //左面的值比key对应的值小 while (left < right && arr[left] <= arr[key]) { ++left; } swap(&arr[left], &arr[right]); } swap(&arr[left], &arr[key]); key = left; //这样子就会使得key对应的值到达正确的位置 //开始用begin和end分别保存左右端点值 //[left,key-1] key [key+1,right] QuickSort(arr, begin, key - 1); QuickSort(arr, key + 1, end); }
我们知道快速排序的时间复杂度为O(N*logN),但是当数组本身有序或接近有序时的逆序就会导致时间复杂度变成O(N^2),因此我们可以对这种情况进行优化。
//随机取key法
int randi = rand() % (right - left + 1);
randi += left;
swap(&arr[randi], &arr[left]);
int key = left;
int GetMideNum(int* a,int left,int right) { int mid = (left + right) / 2; if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else { return right; } } else // a[left] > a[mid] { if (a[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } } } int randi = GetMideNum(arr, left, right); swap(&arr[left], &arr[randi]); int key = left;
此外,除了时间复杂度的问题,还有空间复杂度的问题。我们知道快排的最后一层函数栈帧的建立就占了全部的50%。因此我们可以进行小区间优化,减少栈帧的浪费,这里可以采用小区间采用插入排序(当数据有序或接近有序时,插入排序处理的很快)。
if (right - left + 1 < 10)
{
InsertSort(arr, right - left + 1);
}
//升序 //快速排序 void QuickSort(int* arr, int left, int right) { if (left >= right) { return; } int begin = left, end = right; int cur = left+1, prev = left; int key = left; //一趟排序 while (cur <= right) { if (arr[cur] < arr[key] && ++prev != cur) swap(&arr[prev], &arr[cur]); ++cur; } swap(&arr[key], &arr[prev]); key = prev; //[left,key-1] key [key+1,right] QuickSort(arr, begin, key - 1); QuickSort(arr, key + 1, end); }
void QuickSortNonR(int* a, int left, int right) { ST st; STInit(&st); STPush(&st, right); STPush(&st, left); while (!STEmpty(&st)) { int begin = STTop(&st); STPop(&st); int end = STTop(&st); STPop(&st); // 单趟 int keyi = begin; int prev = begin; int cur = begin + 1; while (cur <= end) { if (a[cur] < a[keyi] && ++prev != cur) Swap(&a[prev], &a[cur]); ++cur; } Swap(&a[keyi], &a[prev]); keyi = prev; // [begin, keyi-1] keyi [keyi+1, end] if (keyi + 1 < end) { STPush(&st, end); STPush(&st, keyi + 1); } if (begin < keyi-1) { STPush(&st, keyi-1); STPush(&st, begin); } } STDestroy(&st); }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。