开发者学堂课程【你的第一门 C 语言课：快速排序】学习笔记，与课程紧密联系，让用户快速学习知识
课程地址：https://developer.aliyun.com/learning/course/444/detail/5485
快速排序
目录：
一、分治法
二、排序
三、快速排序法
一、分治法
1、分治法
(1)、大事化小，小事化了：把一件事情，分成各个小部分，在进行处理。
(2)、递归就是分治法的实现。把一个大的问题分成若干个小的问题，再把小的问题分成更小的问题，直到不能再分，从最简单的那个问题入手解决，层层回归，到最后大问题自然也就解决了。
(3)、例子：
比如国家要统计 GDP 总和，而你是这件事的负责人，你可以怎么做？可以找一张大的中国地图，然后自东向西、从南到北派下属去遍历每一寸国土，最后把所有的GDP 加起来就是一个总和。
但是这个很耗费物力人力，不建议这样做。那在现实中，可以将国家分成各个省市，再把省市分成各个区县。区县再分为乡镇，从乡镇开始统计，层层统计，向上汇报，最后加起来就是整个国家 GDP 的总和。这就是分治事项。如果要对整个国家的 GDP 进行排名，那么就需要排序算法了，以下以此为论点展开讲述。
二、排序
1、排序就是将一堆零零散散的数据重大到小、从小到大排成一个序列。
2、排序用的地方很多：
例如：
（1）期末考试老师要给所有同学的成绩进行一个排序，排出前几名拿奖学金和后几名叫家长；
（2）打开招聘网站经常就会优先考虑待遇较高的或者待遇较低的职位，肯定是待遇较高的，那么就应该对薪酬从高到低进行排序；
（3）在淘宝中购买化妆品，但不知道哪一款合适，所以可以点销量进行排序；
（4）排序的方法有很多，比如，耳熟能详的冒泡排序、鸡尾酒排序、插入排序、选择排序、快速排序等。
三、快速排序算法
1、快速排序是20世纪十大算法之一。
快速排序算法的基本思想是:通过一趟排序将待排序数据分割成独立的两部分，其中一部分的所有元素均比另一部分的元素小，然后分别对这两部分继续进行排序，重复上述步骤直到排序完成。
1) 现在就要把他分割成两部分，然后就需要去找基准点 ，起始是0，最后是9，（0+9）/2=4，那么下标就应该是4的位置，然后选择中间元素7作为基准点。
2) i 是从左往右走的下标，j 是从右往左走的下标，从左往右找到大于等于基准点的元素。
3) 从右到左找到小于等于基准点的元素。
4) 两个元素进行互换
5) 从左往右找到大于等于基准点的元素
6) 从右往左找打小于等于基点的元素
7) 两个元素进行互换
8) 从左往右找到大于等于基点的元素
从右往左找打小于等于基点的元素
9) 两个元素进行互换
10) 一直重复这三个相同的步骤，直到 i > j。第一趟结束
11) 按照第一趟的方法递归左边和右边两个例子
12) 排序完成
实现代码：
#include
void quick_sort(int array[], int Left, int right )
{
inti=left,j=right;
int temp;
int pivot ;
pivot = array[(Left + right) / 2];
while (i <= j)
{
//从左到右找到大于等于基准点的元素
while (array[i] < pivot)
i++;
}
//从右到左找到小于等于基准点的元素
while (array[j] > pivot)
{
j--;
}
//如果主<= j，则互换
if(i<=j)
{
temp = array[i];
array[i] = array[j] ;
arraylj] = temp;
i++ ;
j-- ;
}
}
if (Left < i)
{
quick_ sort(array, Left, j) ;
}
if (i < right)
{
quick_ sort(array, i, right) ;
}
int main( void)
{
int array[] = {73, 108， 111, 118， 101, 70, 105，115, 104，67，46，99，111, 109};
int i, Length ;
Length = sizeof(array) / sizeof(array[0]);
quick sort(array, 0, length-1);
printf("排序后的结果是: ");
for (i = 0; i < Length; i++)
{
printf("Sd ”，array[i]);
}
putchar('\n')
return 0 ;
}
运行：gcc quick sort.c && ./a. out
排序后的结果效果图:
序列被分为两个序列，左边的都小于等于基点，右边的大于等于基点，然后进行递归。
