快排算法的一点思考

佚名 4年前 (2020-05-06) 算法 525人围观抢沙发百度已收录

基础的快排算法是很常用且效率高的排序算法，而且在一些面试和考试中也用得到，故在尝试实现基础的快排算法后写下此文。

1、整体代码（主要根据算法导论的快排章节的思想）：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include <stdio.h> #include <stdlib.h>
#define M 15
void QuickSort(int A[],int p,int r);//递归实现的主程序 int PARTITION(int A[],int p,int r);//局部排序的函数 int main(){ int i = 0; int a[M] = {3,9,1,6,5,98,15,47,11,24,35,12,4,78,36}; printf("start: "); for(i = 0;i<M;i++){ printf("%3d",a[i]); } printf("\n"); QuickSort(a,0,M-1); printf("end : "); for(i = 0;i<M;i++){ printf("%3d",a[i]); } return 0; } void QuickSort(int A[],int p,int r){ int q = 0; if(p < r){ q = PARTITION(A,p,r);
 //递归实现子串排序 QuickSort(A,p,q-1); QuickSort(A,q+1,r); } } int PARTITION(int A[],int p,int r){ int x = A[r];//选定标记位（这边是选定了需要排序的最后一位） int i = p-1,j=p,temp; for(j = p;j < r;j++){
 //将小于标记位的数字与前面的数字进行交换，这样使得数组前面变成小于标记位的数字 if(A[j] <= x){ i++; temp = A[j]; A[j] = A[i]; A[i] = temp; } }
 //最后把标记位数字（这里是选定了最后一位）与前面大于标记位的数字进行交换（不存在大于的话就是和自己交换） temp = A[r]; A[r] = A[i+1]; A[i+1] = temp;
 return i+1;//返回当前标记位数字的位置 }

执行结果：

start:   3  9  1  6  5 98 15 47 11 24 35 12  4 78 36 end : 1  3  4  5  6  9 11 12 15 24 35 36 47 78 98

2、主要思路

快速排序（Quicksort）是对冒泡排序的一种改进，大多通过递归实现，是一种不稳定的排序算法。

主要思路是根据分治法的原则，把一整串数据拆分多次，实现大事化小从而进行排序。

具体的思想为，从一串数据中选定一个标志数据，在一次排序之中，使其前面的数字都比起小，后面的数字都比其大，并对前面的数字串和后面的数字串执行程序，反复直至确定所有元素的位置。

3、不稳定性的理解

从思想中可以看出，每调用一次局部排序的函数，就有一个元素确定位置，因为递归的缘故，所以平均时间复杂度O(nlogn)，且是一种不稳定的算法

因为对于相同的数字，如果把后面的数字作为标记，前面的数字判定为<=,后面的数字就应该与前面的数字交换位置，导致数字顺序颠倒成为不稳定的排序。（这里可能有人会想，如果相等不交换不就是变成稳定的了? 很遗憾，并不可以，如果相等的值不触发交换，那么就可能出现标记数前后都有与标记数等值的数字，那么排序就失败了）

一个例子（标红的6本来在后面）

3 9 1 6 6

经过排序后

3 1 6 9 6

4、对递归的理解

我给局部函数加了一个输出，就是每次调用函数时输出排序的数字在数组的位置，这样便于理解递归的调用。

void QuickSort(int A[],int p,int r){ int q = 0; if(p < r){ q = PARTITION(A,p,r); QuickSort(A,p,q-1); QuickSort(A,q+1,r); } }

int PARTITION(int A[],int p,int r){ int x = A[r]; int i = p-1,j=p,temp; for(j = p;j < r;j++){ if(A[j] <= x){ i++; temp = A[j]; A[j] = A[i]; A[i] = temp; } } temp = A[r]; A[r] = A[i+1]; A[i+1] = temp;
 //添加的简单输出 printf("(%2d-%2d)",p,r); for(j = p;j<=r;j++){ printf("%3d",A[j]); } printf("\n"); return i+1; }

输出：

start:   3  9  1  6  5 98 15 47 11 24 35 12  4 78 36 ( 0-14)  3  9  1  6  5 15 11 24 35 12  4 36 98 78 47 ( 0-10)  3  1  4  6  5 15 11 24 35 12  9 ( 0- 1)  1  3 ( 3-10)  6  5  9 11 24 35 12 15 ( 3- 4)  5  6 ( 6-10) 11 12 15 24 35 ( 6- 7) 11 12 ( 9-10) 24 35 (12-14) 47 78 98 (13-14) 78 98 end : 1  3  4  5  6  9 11 12 15 24 35 36 47 78 98