快速排序
hoare版本
1.设置最左边（或最右边）一个值为key，把比key小的key的放在key左边，大于key的放在key右边，这里key是6
2.如何保证相遇位置比key要小，让R先走即可，这种情况是让左边第一个做key，同理右边第一个做key，让L先走，即可在小于K处相遇
3.相遇之后交换相遇位置的数和key所指的数即可
int PartSort(int* arr, int left, int right) { int keyi = left; while (left < right) { while (left < right && arr[right] >= arr[keyi])//left<right是为了防止这俩个错过 { right--; } while (left < right && arr[left] <= arr[keyi]) { left++; } if (left<right) Swap(&arr[left], &arr[right]); } int meeti = left; Swap(&arr[meeti], &arr[keyi]); return meeti; }
单趟排序
要对所有数据排序，进行递归即可
如何递归？
将keyi左边先递归排序，然后再右边
int PartSort(int* arr, int left, int right) { int keyi = left; while (left < right) { while (left < right && arr[right] >= arr[keyi])//left<right是为了防止这俩个错过 { right--; } while (left < right && arr[left] <= arr[keyi]) { left++; } if (left<right) Swap(&arr[left], &arr[right]); } int meeti = left; Swap(&arr[meeti], &arr[keyi]); return meeti; } //部分排序 void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; //如果左指针>=右指针，返回 } int keyi=PartSort(a, begin, end); QuickSort(a, begin, keyi - 1);// QuickSort(a, keyi+1, end); } //快排 int main() { int arr[] = {9,1,2,5,7,4,8,6,3,5 }; int n = sizeof(arr) / sizeof(arr[0]); QuickSort(arr, 0, n - 1); return 0; }
当每次选key为中间值时，递归深度：logN，每次单趟排序合计起来个数是N，时间复杂度：O(N*logN)。
快排比堆排，希尔排序略胜一筹
单趟排序，如果选中间做key，如果还有一个大小为key的值在key的左边或右边，就不好搞。
如果有序/接近有序，选左边排序，比key大的在左边，没有比key小的，key的左边为空，之后递归右边
如果这样一直往下走，树的高度是N，每次递归都会少一个数
时间复杂度：O(N^2)
debug,N=10000,就会栈溢出，此时换realse（100000个数据）版本看O(N^2)情况下的运算情况
100W个数据
优化选key逻辑：1.随机选一个位置做key（如果每次选最左边或最右边有可能会发生跟上面O(N^2)一样的情况，但如果随机选位置就算有序，每次选的数不一定是最左边或最右边）
2.针对有序情况，选正中间的值做key，之后把key和最左边或最右边的交换即可
3.三数取中，第一个位置，中间位置，和最后一个位置，选出这三个位置上的中间数据值，然后再跟最左边数据交换
void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } int GetMindIndex(int* arr, int left, int right) { int mid = (right + left) / 2; if (arr[left] < arr[mid]) { if (arr[mid] < arr[right]) return mid; else if (arr[right]<arr[left]) return left; else return right; } else { if (arr[mid] > arr[right]) return mid; else if (arr[right] > arr[left]) return left; else return right; } } int PartSort(int* arr, int left, int right) { int mid = GetMindIndex(arr, left, right); Swap(&arr[mid], &arr[left]); int keyi = left; while (left < right) { while (left < right && arr[right] >= arr[keyi])//left<right是为了防止这俩个错过 { right--; } while (left < right && arr[left] <= arr[keyi]) { left++; } if (left<right) Swap(&arr[left], &arr[right]); } int meeti = left; Swap(&arr[meeti], &arr[keyi]); return meeti; } void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } int keyi = PartSort(a, begin, end); QuickSort(a, begin, keyi - 1);// QuickSort(a, keyi + 1, end); } int main() { int arr[] = { 9,1,2,5,7,4,8,6,3,5 }; int n = sizeof(arr) / sizeof(arr[0]); QuickSort(arr, 0, n - 1); return 0; }
测试1000W个数据
跟上面O(N^2)的相比，提高了不少，不用害怕栈溢出，因为其深度不会太深 ，深度是logN
小区间优化
倒数三层合计占用80%栈帧
这种形态有点像二叉树，最后一层占了一半的调用次数，每次调用就会开辟栈帧，如果倒数第二层有8个数进行排序，则要开辟三层栈帧， 8个值本身就是小范围，调用三层栈帧，调用7-8次递归，比较浪费栈帧空间。付出的代价太大
因此当数据<=8时，我们用插入排序，其余用快排
void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } int GetMindIndex(int* arr, int left, int right) { int mid = (right + left) / 2; if (arr[left] < arr[mid]) { if (arr[mid] < arr[right]) return mid; else if (arr[right]<arr[left]) return left; else return right; } else { if (arr[mid] > arr[right]) return mid; else if (arr[right] > arr[left]) return left; else return right; } } int PartSort(int* arr, int left, int right) { int mid = GetMindIndex(arr, left, right); Swap(&arr[mid], &arr[left]); int keyi = left; while (left < right) { while (left < right && arr[right] >= arr[keyi])//left<right是为了防止这俩个错过 { right--; } while (left < right && arr[left] <= arr[keyi]) { left++; } if (left<right) Swap(&arr[left], &arr[right]); } int meeti = left; Swap(&arr[meeti], &arr[keyi]); return meeti; } void InsertSort(int* a, int n) { for (int i = 0; i < n -1; i++) { int end = i; int tmp = a[end +1]; while (end >= 0) { if (a[end] > tmp) { a[end +1] = a[end]; end --; } else { break; } } a[end +1] = tmp; } } void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } if (end - begin <= 8) { InsertSort(a + begin, end - begin + 1); //a+begin是让从左边开始，每次递归都会导致左边不一样 } else { int keyi = PartSort(a, begin, end); QuickSort(a, begin, keyi - 1);// QuickSort(a, keyi + 1, end); } } int main() { int arr[] = { 9,1,2,5,7,4,8,6,3,5 }; int n = sizeof(arr) / sizeof(arr[0]); QuickSort(arr, 0, n - 1); return 0; }
我们可看到这种写法有所优化
挖坑法
1. 先创建一个变量将坑位的值保留，建立俩个指针，分别指向最左边和最右边，若左边为坑，则右指针先走，反之，左指针先走
2.当右指针遇到比key小的数字，停下来，并把该数字放到hole所指位置 （即填到坑里），自己形成新的坑位
3.然后让左边走，遇到比key大的停下来，把数字填到坑里，然后自己相乘新坑位
void InsertSort(int* a, int n) { for (int i = 0; i < n -1; i++) { int end = i; int tmp = a[end +1]; while (end >= 0) { if (a[end] > tmp) { a[end +1] = a[end]; end --; } else { break; } } a[end +1] = tmp; } } void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } if (end - begin <= 8) { InsertSort(a + begin, end - begin + 1); } else { int keyi = PartSort2(a, begin, end); QuickSort(a, begin, keyi - 1);// QuickSort(a, keyi + 1, end); } } //挖坑法 int PartSort2(int* arr, int left, int right) { int mid = GetMindIndex(arr, left, right); Swap(&arr[mid], &arr[left]); int hole = left; int key = arr[left]; while (left < right) { while (left < right && arr[right] >= key) { right--; } arr[hole]=arr[right]; hole = right; while (left < right && arr[left]<= key) { left++; } arr[hole] = arr[left]; hole = left; } arr[hole] = key; return hole; }
性能跟之前的差不多
前后指针法
1.设置俩个指针和一个key，key用来保存数据，俩个指针一前一后，prev在后，cur在前
2.cur先走，prev接着走，当prev的后一个数字比key大时（也就是cur遇到比key大的数字），prev停下来，cur，继续走，cur遇到比key小的值停下来
3.停下来之后，prev向前走一步，交换俩数字，之后按照这种方法继续走就行，当cur走到数组之外时，停止，prev会在小于key的位置停下
int PartSort3(int* arr, int left, int right) { int mid = GetMindIndex(arr, left, right); Swap(&arr[mid], &arr[left]); int keyi = left; int cur = left + 1; int prev = left; while (cur <= right) { if (arr[cur] < arr[keyi] && ++prev != cur)//等于可以不用动那个值，让他留在哪里 { Swap(&arr[cur], &arr[prev]); } ++cur; } Swap(&arr[keyi], &arr[prev]); return prev; } int main() { int arr[] = { 9,1,2,5,7,4,8,6,3,5 }; int n = sizeof(arr) / sizeof(arr[0]); QuickSort(arr, 0, n - 1); return 0; }
非递归
使用递归方式进行快排时，若递归层数较多，则会造成栈溢出，我们可以用数据结构的“栈”来用非递归实现 
先把起点和终点的下标放进去，这样相当于把第一行的，然后用left和right变量来接收这俩个值，并把这俩个值出栈left=0,right=9
出栈后，进行排序，并返回他们中间数据的下标，由于我们递归的时候是先递归左边，再递归右边，所以用栈实现的时候也是先对左边排序，再对右边排序，但由于栈是先入后出，所以要先把右边压栈，再把左边压栈，这样出去的时候就是左先出，先计算左，然后右出，再计算右，压栈的时候左和右要和程序里面的left和right相对应
我们这里在设计的时候是先给右赋值，后给左赋值，再结合我们先给左半边排序再给右半边排序的规则，我们先压5，再压9，之后先压0，再压3
当中间值下标+1>=右边或者左边+1>=中间值下标的时候我们不需要压栈
比如这里最后一行最左边0 中间值下标 0 最右边 0，如果进行压栈待会出栈会出来2个0，而数组里面只有一个0，会影响程序的正确性
int PartSort3(int* arr, int left, int right) { int mid = GetMindIndex(arr, left, right); Swap(&arr[mid], &arr[left]); int keyi = left; int cur = left + 1; int prev = left; while (cur <= right) { if (arr[cur] < arr[keyi] && ++prev != cur)//等于可以不用动那个值，让他留在哪里 { Swap(&arr[cur], &arr[prev]); } ++cur; } Swap(&arr[keyi], &arr[prev]); return prev; } void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } if (end - begin <= 8) { InsertSort(a + begin, end - begin + 1); } else { int keyi = PartSort3(a, begin, end); QuickSort(a, begin, keyi - 1);// QuickSort(a, keyi + 1, end); } } void QuickSortNonR(int* a, int begin, int end) { ST st; StackInit(&st); StackPush(&st, begin); StackPush(&st, end); while (!StackEmpty(&st)) { int right = StackTop(&st); StackPop(&st); int left = StackTop(&st); StackPop(&st); int keyi = PartSort3(a, left, right); // [left, keyi-1] keyi [keyi+1,right] if (keyi + 1 < right)//限制条件 { StackPush(&st, keyi + 1); StackPush(&st, right); } if (left < right - 1) //限制条件 { StackPush(&st, left); StackPush(&st, keyi - 1); } } StackDestory(&st); } int main() { int arr[] = {1,2,3,4,5,6,7,8,9,10 }; int n = sizeof(arr) / sizeof(arr[0]); QuickSortNonR(arr, 0, n - 1); return 0; }
