快速排序（2）

快速排序（2）

快速排序的优化（小区间优化）

sort.h

#include <stdio.h>void PrintArray(int *a,int n);
void Swap(int *x,int *y);//原版
int PartSort(int *a,int left,int right);//快速排序
void QuickSort(int *a,int left,int right);//直接插入排序
void InsertSort(int *a,int n);
void InsertSort1(int *a,int n);

sort.c

#include "sort.h"void PrintArray(int *a,int n)
{for(int i=0;i<n;i++){printf("%d ",a[i]);}printf("\n");
}
void Swap(int *x,int *y)
{int tmp=*x;*x=*y;*y=tmp;
}//原版
int PartSort(int *a,int left,int right)
{int key_i=left;while(left<right){while(left<right&&a[right]>=a[key_i]){right--;}while(left<right&&a[left]<=a[key_i]){left++;}Swap(&a[left],&a[right]);}Swap(&a[key_i],&a[left]);return left;
}
//直接插入排序
void InsertSort(int *a,int n)
{if(n<=1)return ;for(int i=0;i<n-1;i++){int end=i;int tmp=a[end+1];while(end>=0){if(a[end]>tmp){a[end+1]=a[end];}else{break;}end--;}a[end+1]=tmp;}
}
//直接插入排序
//这个是我复现插入排序的时候额外写的，应该是没什么问题的，我试过了
void InsertSort1(int *a,int n)
{if(n<=1)return ;for(int i=0;i<n-1;i++){int end=i;while(end>=0){//int tmp=a[end+1];if(a[end]>a[end+1]){Swap(&a[end],&a[end+1]);}else{break;}end--;}}
}
//快速排序
void QuickSort(int *a,int left,int right)
{if(left>=right)return;if(right-left+1<=10){/*这里为啥要a+left呢，假设数组54321，一趟排序之后，分成21一组，54一组，21那一组的数组的开头是不是就得是a+left才能插入排序21这一组昂。或者自己过一遍这个代码流程，就明白了。*/InsertSort(a+left,right-left+1);}else{int key_i= PartSort(a,left,right);QuickSort(a,left,key_i-1);QuickSort(a,key_i+1,right);}
}

test.c

#include "sort.h"void Test1()
{int a[]={23,18,30,11,2,19,28,4,21,14,6,26,9,16,5,24,13,20,10,3,22,29,15,7,1,25,27};QuickSort(a,0, sizeof(a)/ sizeof(int)-1);PrintArray(a, sizeof(a)/ sizeof(int));
}
void Test2()
{int a[]={6,1,2,7,9,3,4,5,10,8};InsertSort1(a,sizeof(a)/ sizeof(int));PrintArray(a, sizeof(a)/ sizeof(int));
}
int main()
{Test1();return 0;
}

快速排序的非递归写法

为什么要用非递归的方式去实现快速排序呢？主要就是怕栈溢出这个问题，但是一般情况下是不会栈溢出的。这里一方面是为了学习，一方面是是为了应付在一些极限条件下，不得不使用非递归的情况。

关于“栈溢出”这个词，我会讲完排序之后，给大家介绍一下。或者大家也可以先去问一下AI。

所以我们就得用一个数据结构来把这个参数给存起来。那么我们这里用的是啥数据结构呢？那就是栈。主要是借助了栈的后进先出的特点。在这里使用栈来存储要排序的数列的边界，这样就可以使用非递归的方式但是遵循递归的思想去实现快速排序：

sort.h

#include <stdio.h>void PrintArray(int *a,int n);
void Swap(int *x,int *y);//原版
int PartSort(int *a,int left,int right);//快速排序
void QuickSort(int *a,int left,int right);

sort.c

#include "sort.h"
#include "stack.h"
void PrintArray(int *a,int n)
{for(int i=0;i<n;i++){printf("%d ",a[i]);}printf("\n");
}
void Swap(int *x,int *y)
{int tmp=*x;*x=*y;*y=tmp;
}//原版
int PartSort(int *a,int left,int right)
{int key_i=left;while(left<right){while(left<right&&a[right]>=a[key_i]){right--;}while(left<right&&a[left]<=a[key_i]){left++;}Swap(&a[left],&a[right]);}Swap(&a[key_i],&a[left]);return left;
}//非递归实现快速排序
void QuickSort(int *a,int left,int right)
{SK sk;SKInit(&sk);SKPush(&sk,right);SKPush(&sk,left);while(!SKEmpty(&sk)){int begin=SKTop(&sk);SKPop(&sk);int end= SKTop(&sk);SKPop(&sk);int key_i= PartSort(a,begin,end);// [begin,key_i-1] key_i [key_i+1, end]if(key_i+1<end){SKPush(&sk,end);SKPush(&sk,key_i+1);}if(begin<key_i-1){SKPush(&sk,key_i-1);SKPush(&sk,begin);}}SKDestroy(&sk);
}

stack.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int SKDataType;
typedef struct Stack
{SKDataType *a;int top;//标记栈顶的工具int capacity;//容量
}SK;//初始化栈
void SKInit(SK* ps);
//销毁栈
void SKDestroy(SK* ps);//插入数据，压栈
void SKPush(SK* ps,SKDataType x);
//删除数据，出栈
void SKPop(SK* ps);
//获取现在栈顶元素的值
SKDataType SKTop(SK* ps);//栈的大小
int SKSize(SK* ps);
//判断栈是否为空
bool SKEmpty(SK* ps);

stack.c

#include "stack.h"//初始化栈
void SKInit(SK* ps)
{assert(ps);ps->a=NULL;ps->capacity=0;ps->top=0;
}//销毁栈
void SKDestroy(SK* ps)
{assert(ps);free(ps->a);ps->a=NULL;ps->top=ps->capacity=0;
}//插入数据，压栈
void SKPush(SK* ps,SKDataType x)
{assert(ps);if(ps->top==ps->capacity){int newCapacity=ps->capacity==0 ? 4 :ps->capacity*2;SKDataType * tmp=(SKDataType*) realloc(ps->a,sizeof (SKDataType)*newCapacity);if(tmp==NULL){perror("realloc failed");exit(-1);}ps->a=tmp;ps->capacity=newCapacity;}ps->a[ps->top]=x;ps->top++;
}//删除数据，出栈
void SKPop(SK* ps)
{assert(ps);assert(ps->top>0);ps->top--;
}//获取现在栈顶元素的值
SKDataType SKTop(SK* ps)
{assert(ps);assert(ps->top>0);return ps->a[ps->top-1];
}//栈的大小
int SKSize(SK* ps)
{assert(ps);return ps->top;
}//判断栈是否为空
bool SKEmpty(SK* ps)
{assert(ps);return ps->top==0;
}

test.c

#include "sort.h"
//#include "stack.h"
void Test1()
{int a[]={6,1,2,7,9,3,4,5,10,8};QuickSort(a,0, sizeof(a)/ sizeof(int)-1);PrintArray(a, sizeof(a)/ sizeof(int));
}int main()
{Test1();return 0;
}