快速排序

思想：

它是由冒泡排序改进而来的。在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录放入适当位置后,数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间(称为该记录归位),这个过程称作一趟快速排序。

说明：最核心的思想是将小的部分放在左边，大的部分放到右边，实现分割。

---

时间复杂度：

最好情况 ：O(nlogn) 最坏情况 ：O(nlog2n) 因为每次都将序列分为两个部分(一般二分都复杂度都和logN相关)

空间复杂度：(nlog2n)

---

稳定性：

原来的顺序就可能被打乱。如序列为 5 3 3 4 3 8 9 10 11会将3的顺序打乱。所以说，快速排序是不稳定的！

---

#include<stdio.h> void printArray(int a[], int size) //打印数组元素 { int i; for(i = 0; i < size; i++) printf("%d ",a[i]); printf("\n"); } void quick_sort(int array[],int left,int right) //left第一个元素的下标，,right最后一个元素的下标 { int i,j,t,temp; if(left>right) //左端只剩下最后一个元素时，上一层递归语句中left>right-1此元素无需排序 即跳出函数,右端只剩下最后一个元素的上一层递归语句中left+1>right 此元素无需排序 即跳出函数 return ; temp=array[left]; //temp中存的就是基准数 i=left; j=right; while(i!=j) //确保小的数据在基准的左边，大的数据在基准的右边 { //顺序很重要，要先从右边开始找 while(array[j]>=temp && i<j) //寻找小于基准的元素 j--; //再找右边的 while(array[i]<=temp && i<j) //寻找大于基准的元素 i++; if(i<j) //交换两个数在数组中的位置 { t=array[i]; array[i]=array[j]; array[j]=t; } } array[left]=array[i]; //最终将新基准数array[i]放在左端 array[i]=temp; //将基准放在i处，使得i左段的值小于i，右端的值大于 i printArray(array,10); quick_sort(array,left,i-1);//继续处理左段的，这里是一个递归的过程 quick_sort(array,i+1,right);//继续处理右段的 ，这里是一个递归的过程 } int main() { int count=10,a[10]={3,0,1,8,7,2,5,4,9,6}; printArray(a,count); quick_sort(a,0,count - 1); }

---