排序算法-----快速排序（非递归实现）

前言

快速排序

基本思路

非递归代码实现

前言

很久没跟新数据结构与算法这一栏了，因为数据结构与算法基本上都发布完了，哈哈，那今天我就把前面排序算法那一块的快速排序完善一下，前面只发布了快速排序递归算法，那这一次就去用非递归来去实现。（递归算法：排序算法-----快速排序（递归）_快排递归_Gretel Tade的博客-CSDN博客）

快速排序

快速排序（Quicksort），计算机科学词汇，适用领域Pascal，C++等语言，是对冒泡排序算法的一种改进。

快速排序采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素pivot，利用pivot将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列排列成有序序列。

基本思路

现在给定一个数组初始 [25,24,6,65,11,43,22,51] ，然后进行快速排序

第一步，先选取一个参考数字temp，一般选取第一个即temp=25，然后标记最左边和最右边数字的位置分别为i, j

25 24 6 64 11 43 22 51

i j

temp

第二步，先去向左移动j 的位置，当j指向的数字小于temp时候，就停止移动，然后开始向右移动i

当i 移动到比temp要大的数字时，停止移动，此时将i 和 j 指向的数字进行交换，如下所示：

25 24 6 64 11 43 22 51

temp i j

交换后：

25 24 6 22 11 43 65 51

temp i j

第三步，此时，开始接着移动 j，当j 移动到比temp要小的数字的时候，停止移动, 如下所示：

25 24 6 22 11 43 65 51

temp i j

然后开始移动i ，当i 移动到与j 相遇的位置时，i停止移动（如果i 移动到比temp要大的数字的时候就执行上面的第二步，i与j 进行数字交换）

25 24 6 22 11 43 65 51

temp i,j

第四步，此时，i与j指向的数字与temp指向的数字进行数字交换

11 24 6 22 25 43 65 51

temp i,j

这时候我们会发现，此时i和j指向的数字的位置，左边的都比这个数字要小，右边的都比这个数字要大，于是我们就可以去进入到递归，分别对左边和右边的数字进行以上步骤的递归，最后两边的数字都会被排好序。

动态图

非递归代码实现

#include<stdio.h>
#include<stdlib.h>
//每一趟排序
int sort(int* arr, int left, int right) {int i = left;int j = right;int temp = arr[left];while (i != j) {while (temp <= arr[j] && i < j)//j左移j--;while (temp >= arr[i] && i < j)//i向右移i++;if (i < j) {//i与j都停止移动的时候，交换数字int t = arr[i];arr[i] = arr[j];arr[j] = t;}}//此时i与j相遇，进行数字交换arr[left] = arr[i];arr[i] = temp;return i;//返回这个交汇点
}void quick_sort(int* arr, int left, int right) {int* stack = (int*)malloc(sizeof(int) * right);//创建一个数组栈for (int i = 0; i < right; i++)stack[i] = -1;//初始化为-1int count = 0;//当前栈数据的个数if (left < right) {//入栈stack[count++] = left;stack[count++] = right;}while (count) {//当栈为非空的时候//出栈操作int r_pop = stack[count-1];int l_pop = stack[count-2];stack[count - 1] = stack[count - 2] = -1;//出栈后，清空已出栈数据，设置为-1count -= 2;int i = sort(arr, l_pop, r_pop);//如果这个交汇点前面数据的下标比当前最左边的数据下标要大的话，就入栈if (l_pop < i - 1) {stack[count++] = l_pop;stack[count++] = i - 1;}//如果这个交汇点后面一个数据的下标比当前最右边数据的下标要小的话，入栈if (r_pop > i + 1) {stack[count++] = i + 1;stack[count++] = r_pop;}}//释放空间free(stack);stack = NULL;
}int main() {int array[8] = { 25,24,6,65,11,43,22,51 };printf("排序前:");for (int i = 0; i < sizeof(array) / sizeof(int); i++) {printf("%d ", array[i]);}printf("\n排序后：");quick_sort(array, 0, sizeof(array) / sizeof(int) - 1);for (int i = 0; i < sizeof(array) / sizeof(int); i++) {printf("%d ", array[i]);}
}

运行结果：