本文共 4349 字，大约阅读时间需要 14 分钟。
一、快速排序
1、知识点:
每次的枢轴都把表等分为长度相近的两个子表时，速度是最快的；当表本身已经有序或逆序时，速度最慢。
2、递归实现 摘自：
https://blog.csdn.net/qq_36528114/article/details/78667034?utm_medium=distribute.pc_relevant.none-task-blog-OPENSEARCH-2.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-OPENSEARCH-2.nonecase
3、非递归实现
C语言版本
#include typedef struct node{ int min; int max;}Node;#define MaxSize 50 void sort(int a[], int min, int max){ int k = a[min]; int i = min; int j = max; int temp; Node Stack[MaxSize]; int top = 0; Stack[top].min = min; Stack[top].max = max; while (top > -1) { // min max记录当前处理的这个区间的左极限和右极限 i = min = Stack[top].min; j = max = Stack[top].max; top--; k = a[min]; while (i =a[i]) { i++; } if (i < j) { temp = a[i]; a[i] = a[j]; a[j] = temp; j--; } if (min < i - 1) { top++; Stack[top].min = min; Stack[top].max = i-1; } if (max>i + 1) { top++; Stack[top].min = i + 1; Stack[top].max = max; } } } } int main(){ int i; int a[10] = { 49, 38, 65, 97, 76, 13, 27, 9, 2, 1 }; for ( i = 0; i < 10; i++) { printf("%d\t", a[i]); } printf("\n"); sort(a, 0, 9); for ( i = 0; i < 10; i++) { printf("%d\t", a[i]); } printf("\n"); getchar();}
java版本
import java.util.Stack; public class QuickSort { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub QuickSort t=new QuickSort(); t.test(); } public void test(){ int a[]={ 10,1,4,7,8,6,13,41,4,34,5,9,2}; printArray(a); nonRecrutSort(a); // nonRecrutQuickSort(a); printArray(a); } public void nonRecrutSort(int[] a){ //非递归快排，两个栈 //设置两个栈，一个用于保存 if(a==null||a.length<0) return; Stack startStack=new Stack ();//保存当前划分的最高位 Stack endStack=new Stack ();//保存当前划分的最低位 int start=0; int end=a.length-1; int pivotPos; startStack.push(start); endStack.push(end); while(!startStack.isEmpty()){ start=startStack.pop(); end=endStack.pop(); pivotPos=partition(a, start, end); if(start pivotPos+1){ startStack.push(pivotPos+1); endStack.push(end); } } } public void nonRecrutQuickSort(int a[]){ if(a==null||a.length<=0)return; Stack index=new Stack (); //用一个栈存储分界点位置的 int start=0; int end=a.length-1; int pivotPos; index.push(start); index.push(end); while(!index.isEmpty()){ end=index.pop(); start=index.pop(); pivotPos=partition(a,start,end); if(start pivotPos+1){ index.push(pivotPos+1); index.push(end); } } } public int partition(int[] a,int start,int end){ //分块方法，在数组a中，对下标从start到end的数列进行划分 int pivot=a[start]; //把比pivot(初始的pivot=a[start]小的数移动到pivot的左边 while(start =pivot) end--; a[start]=a[end]; while(start <=pivot) start++; a[end]=a[start]; } a[start]=pivot; return start;//返回划分后的pivot的位置 //printArray(a); } public void printArray(int a[]){ //打印数组内容的方法，用于测试 for(int i=0;i 二、随机快速排序：
三、例题
1、荷兰国旗问题：设有一个仅由红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O（n）的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。
typedef enum{ RED,WHITE,BLUE} color;//设置枚举数组 void Flag_Arrange(color a[],int n){ int i=0,j=0,k=n-1; while(j<=k){ switch(a[j]){ //判断条块颜色 case RED:Swap(a[i],a[j]);i++;j++;break; //红色，则和i交换 case WHITE:j++;break; case BULE:Swap(a[j],a[k]);k--; //蓝色，则和k交换 } }} /** * 荷兰国旗问题 * * 给定一个数组arr，和一个数num，请把小于num的数放在数组的 左边， * 等于num的数放在数组的中间， * 大于num的数放在数组的 右边。 * 要求额外空间复杂度O(1)，时间复杂度O(N) * */ public static int[] partition(int[] arr, int L, int R, int num) { //假设的第一个指针位置 int less = L-1; //假设的第二个指针位置 int more = R+1; //元素num所比较的位置 int index = L; while(index 数组元素时的情况 swap(arr,++less,index++); }else if(arr[index]>num) { //more--; //当大于num时,由于右半边界的数未知,所以保持数组不变 swap(arr,--more,index); }else { //相等的情况 index++; } } //返回交换后的边界 return new int[] { less+1,more-1}; } //交换函数 public static void swap(int[] arr,int L,int R) { int t = arr[L]; arr[L] = arr[R]; arr[R] = t; }