快速排序递归和非递归方法的简单介绍

基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

实现快速排序的单趟排序中有三种方法：1. 左右指针法；2. 挖坑法；3. 前后指针法

1. 左右指针法：其基本思想就是begin指针指向数组的首元素，begin作用是找大于key的值；end指针指向数组的末尾元素，end作用是找小于key的值；key为基准值此时选择末尾元素作为基准值（选择首元素作为基准），那么需要左边先走也就是begin先移动（那么需要右边先走也就是end移动）。begin找到大于key的值就和end位置的值交换（end找到小于begin的值就和begin位置的值交换），直到begin和end相遇，相遇后此位置就是key再数组最终有序后的位置。

画图举例：如下图所示key=8到了正确的位置，将数组分为左右两部分，然后递归调用单趟（第一趟）排序的方法即可。注意：选右（左）边为基准一定要让左（右）边先走，否则会出问题，具体画图得知

// 交换两个数
void Swap(int* q1, int* q2)
{int temp = *q1;*q1 = *q2;*q2 = temp;
}// 单趟 左右指针法
int partionsort1(int* arr, int begin, int end)
{assert(arr);// 以下两行代码是三数取中间值解决快速排序最坏的情况的时间复杂度，后面讲到了取消注释即可//int midIndex = Getmidindex(arr, begin, end);//Swap(&arr[midIndex], &arr[end]);int keyindex = end; // 选右边则begin左边先走反之右边先走while (begin < end){// begin先走 找大while (begin < end && arr[begin] <= arr[keyindex]) // 不加=号可能会导致死循环{++begin;}// end 找小while (begin < end && arr[end] >= arr[keyindex]){--end;}Swap(&arr[begin], &arr[end]);}Swap(&arr[begin], &arr[keyindex]);return begin;
}

2. 挖坑法：

选择end位置为初始坑，用key保存end位置的值，begin移动找到大于key的值，将该值放到end处，此时begin处就是新的坑（数据可以被覆盖）；然后end移动找到小于key的值，将该值放到begin处，此时end处就是新的坑（数据可以被覆盖）。重复下去直到begin和end相遇。key放到他们相遇后的位置即可

画图举例：

// 方法2 挖坑法--这个方法比较好理解
int partionsort2(int* arr, int begin, int end)
{assert(arr);//int midIndex = Getmidindex(arr, begin, end);//Swap(&arr[midIndex], &arr[end]);// 第一个坑，初始坑，end位置就是坑，数据可以被覆盖int key = arr[end];while (begin < end){while (begin < end && arr[begin] <= key){begin++;}// 左边的值比key大，将begin的值填到end的坑上，begin位置就形成了新的坑arr[end] = arr[begin];while (begin < end && arr[end] >= key){end--;}// 右边的值比key小，将end的值填到begin的坑上，end位置就形成了新的坑arr[begin] = arr[end];}// begin和end相遇后就是 这个位置就是坑，也就是key的最终位置arr[begin] = key;return begin;
}

3. 前后指针法：

选择最后一个位置作为基准值key，prev指针指向首元素的前一个位置，cur指针指向首元素，当cur位置的数据小于key时，并且prev+1不等cur时将prev和cur位置的值互换，然后cur++；不进行互换时cur也++。当cur走到end位置后，只需要将key的值和prev+1位置的值互换即可。

画图举例：

// 方法3 前后指针法
int partionsort3(int* arr, int begin, int end)
{assert(arr);//int midIndex = Getmidindex(arr, begin, end);//Swap(&arr[midIndex], &arr[end]);int keyindex = end;int prev = begin - 1;int cur = begin;while (cur < end){if (arr[cur] < arr[keyindex] && ++prev != cur)Swap(&arr[cur], &arr[prev]);cur++;}// 画图演示，最后是要将key和prev的下一个位置的数据进行交换，key的左边才小于key右边才大于keySwap(&arr[++prev], &arr[keyindex]);return prev;
}

递归方法：

利用函数递归调用以上三种方法中的其中一种即可：第一调用时，数组被分为了小于key的前半部分和大于key的后半部分，分别在调用函数对这两部分进行排序即可

void QuickSort1(int* arr, int left, int right)
{assert(arr);if (left >= right)return;int div = partionsort1(arr, left, right);// 排左边部分 [left,div-1] div [div+1 right]QuickSort1(arr, left, div - 1);// 排右边部分QuickSort1(arr, div + 1, right);//if (left < right)//{//	int div = partionsort(arr, left, right);//	// 排左边部分//	QuickSort(arr, left, div - 1);//	// 排右边部分//	QuickSort(arr, div + 1, right);//}
}

快速排序的缺点：数据已经有序的情况下每一次都选择左边或者右边作为key，左边或者右边剩下很多数据，要继续排序建栈帧，会导致栈溢出，比如 1w个有序数，就要建1W个栈帧,此时就是最坏的情况。（时间复杂度为 O (n²)）

前面提到三数取中间值的方法就能够解决最坏的情况，基准值被选在数组中间位置，让数组能较为均衡地被划分，快速排序的时间复杂度得以维持在 O (nlogn)。

// 获得前中后三个数中的中间值，解决快速排序的最坏的情况
int Getmidindex(int* arr, int begin, int end)
{assert(arr);int mid = (begin + end) / 2;if (arr[begin] < arr[mid]){if (arr[mid] < arr[end])return mid;else if (arr[begin] > arr[end])return begin;elsereturn end;}else  // arr[begin] > arr[mid]{if (arr[mid] > arr[end])return mid;else if (arr[end] > arr[begin])return begin;elsereturn end;}
}

优化：待排序的区间小于10的时候使用直接插入排序

// 优化
void QuickSort2(int* arr, int left, int right)
{assert(arr);if (left >= right)return;// 区间大于10if ((right - left + 1) > 10){int div = partionsort3(arr, left, right);// 排左边部分 [left,div-1] div [div+1 right]QuickSort2(arr, left, div - 1);  // 左递归// 排右边部分QuickSort2(arr, div + 1, right);  // 右递归}//区间小于10使用插入排序else{InsertSort(arr + left, right - left + 1);}//if (left < right)//{//	int div = partionsort(arr, left, right);//	// 排左边部分//	QuickSort(arr, left, div - 1);//	// 排右边部分//	QuickSort(arr, div + 1, right);//}
}

非递归方法：

递归的实现，就是给每一个递归函数建立函数栈帧，通过压栈的方式存储函数的参数。这里使用栈来模拟函数栈帧。

前面已经讲到了栈的相关实现代码，这里就直接使用了：

画图理解，下图画出了递归的区间变化图，非递归只需要将left和right压入栈中，再取出来即可传给partionsort即可，只要栈不空，那么就有子区间还是无序状态，栈空后数组就排序完成。

// 递归改非递归，1：改循环（斐波那契数列求解）一些简单的递归才能改；2：栈模拟存储数据
// 非递归作用：1：提高效率（建立函数栈帧还是有消耗的，但是对于现代计算机，这个优化微乎其微可以忽略不计）
//           2：递归最大缺陷就是，如果栈帧的深度太深，可能会导致栈溢出，因为系统的栈区空间一般不大在M级别，
//			 数据结构栈模拟非递归， 数据是存储在堆区上面的，堆区空间是G级别的
// 快速排序--非递归方法--利用栈替代栈区（函数栈帧）
void QuickSortNonR(int* arr, int left, int right)
{assert(arr);Stack st;       // 建栈StackInit(&st); // 初始化栈// 将最开始的区间压入栈StackPush(&st, right);StackPush(&st, left);while (!StackEmpty(&st)){// 数组左区间值int begin = StackTop(&st);  // 取栈顶数据StackPop(&st);              // 出栈// 数组右区间值int end = StackTop(&st);StackPop(&st);int div = partionsort2(arr, begin, end);  // 排序// [begin,div-1] div [div+1,end]// 如果剩下待排序的两段区间的元素个数大于1个那么就入栈，再取出来排序// 和递归一样先排左区间再排右区间if (div + 1 < end)  // 右区间，相当于右递归{StackPush(&st, end);StackPush(&st, div+1);}if (begin < div - 1)  // 左区间，相当于左递归{StackPush(&st, div - 1);StackPush(&st, begin);}}StackDetory(&st);
}

结论：

快速排序是一种基于分治思想的高效排序算法，其核心是通过基准值将数组划分为左右两部分，递归处理直至有序。本文详细介绍了三种单趟排序实现方法：1)左右指针法通过双指针交换元素；2)挖坑法通过移动基准值"坑位"；3)前后指针法利用双指针交替移动。针对递归可能导致的栈溢出问题，提出三数取中优化基准值选择，并建议小规模数据使用插入排序。最后介绍了用栈模拟递归的非递归实现，有效避免深度递归风险。各种方法均附有代码实现和图示说明，完整展现了快速排序的优化思路。