详解快排的四种方式

快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素 序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩ 于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列 在相应位置上为⽌。

1、lomuto前后指针法

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}int _QuickSort(int* arr, int left, int right)
{int key = left, slow = left, fast = left + 1;while (fast <= right){if (arr[fast] < arr[key] && ++slow != fast){Swap(&arr[fast], &arr[slow]);}fast++;}Swap(&arr[key], &arr[slow]);return slow;
}void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}int key = _QuickSort(arr, left, right );//左子序列QuickSort(arr,left,key-1);//右子序列QuickSort(arr,key+1,right);
}

2、hoare版本

1）创建左右指针，确定基准值

2）从右向左找出⽐基准值⼩的数据，从左向右找出⽐基准值⼤的数据，左右指针数据交换，进⼊下次 循环

int _QuickSort2(int* arr, int left, int right)
{int key = left;left++;while (left <= right){//left找比key大的值while (left <= right && arr[left] < arr[key]){++left;}//left指向比key大的值//right找比key小的值while (left <= right && arr[right] > arr[key]){--right;}if (left <= right){Swap(&arr[left++], &arr[right--]);}}Swap(&arr[key], &arr[right]);return right;
}

3、挖洞法

int _QuickSort3(int* arr, int left, int right)
{int key = arr[left];int hole = 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;
}

4、非递归快排

void QuickSortNoR(int* arr, int left, int right)
{ST st;STInit(&st);//[left,right],进栈时要right先进left后进这样出栈的顺序才是对的STpush(&st, right);STpush(&st, left);while (!StackEmpty(&st)){//[begin,end]int begin = STtop(&st);STpop(&st);int end = STtop(&st);STpop(&st);int key = begin;int slow = begin;int fast = begin + 1;while (fast<=end){if (arr[fast] < arr[key] && ++slow != fast){Swap(&arr[fast], &arr[slow]);}fast++;}Swap(&arr[slow], &arr[key]);key = slow;//左 [begin,key-1]//右 [key+1,end]if (key + 1 < end){STpush(&st, end);STpush(&st, key + 1);}if (begin < key - 1){STpush(&st, key-1);STpush(&st, begin);}}}