数据结构：算法篇：快速排序；直接插入排序

目录
快速排序
直接插入排序
改良版冒泡排序

---

快速排序

理解：
   ①从待排序元素中选定一个基准元素；
  ②以基准元素将数据分为两部分：（可以将：大于基准元素放左，小于基准元素放右）
  ③对左半部分（从左端到基准数据）进行①②利用；直到数据有序
      即将左端到基准数据作为范围，传入；这个范围又会产生新的范围：左端到基准数据2；
      ……
      直到数据有序
  ④对左半部分（从基准数据到右端）进行①②利用；
  【粗劣分析：便于理解】
  

  右半部分：
  

  
  【深层分析：便于代码】
  遍历直倒有序：
  

  数据有序后返回上一层
  

    代码思绪
    /*
  思绪：
  选定一个基准(默认左端):   用变量temp记录基准值;
  
  loop:
  此时左端所在下标low代表的值可以被覆盖(值已经被复制了)
  从右端向左端的方向,开始与temp比力,直到遇到比temp小的数,(否则就high--左移),将这个小于temp的数(下标可假定为high')放到左边，左边下标low所在的数据上
  
  此时右端所在下标high代表的值可以被覆盖(值已经复制到下标low代表的值内了)
  从左端向左端的方向,开始与temp比力,直到遇到比temp大的数,(否则就low++后移),将这个大于temp的数(下标可假定为low')放到右边，左边下标high所在的数据上
  
  此时左端low'下标的数据可以被覆盖，回到loop;
  
  循环竣事条件:low'后移high'前移 直到相遇，说明以基准值temp将这批数据分成两份完毕。
  
  注意：此时巨细两份固然分类完成，但是 作为基准值的数据 还未找到位置；【基准值应该放在下标为low的位置】
  
  看下面图理解
  注意，此时应low==high并且理应必须low==high，
  注意，此时下标所在位置的数据应该被覆盖，
  故基准值应该放在下标为low的位置(大概下标为high，反正两值相称)
  *********************************************************
  《基准值临界情形图》
  基准值5
  x x x x 6 3 x x x
          l h     此时基准值正在与l所代表元素比力l向右移中（说明h位置是无用数据）
  x x x x 6 6 x x x
          l h     l数据复制给h,轮到下标h向左移动
  x x x x 6 6 x x x
          ↑       两下标重合相称，此时应该放入基准值temp(h现在是无用数据)(low左边比基准值小，high右边比基准值大)
  基准值7
  x x x x 6 5 x x
          l h     此时基准值正在与l所代表元素比力h向左移动中（说明l位置是无用数据）
  x x x x 5 5 x x
          l h     h数据复制给l,轮到下标l向左移动(h现在是无用数据)
  x x x x 5 5 x x
            ↑     两下标重合相称，此时应该放入基准值temp(h现在是无用数据)(low左边比基准值小，high右边比基准值大)
  *********************************************************
  */
  
  全部代码：

1. #include <stdio.h>
3. //显示函数
4. void showData(int buf[],int len)
5. {
6.     //显示
7.     for(int i=0;i<len;i++)
8.         printf("%d ",buf[i]);
9.     printf("\n");
10. }
12. //快速排序函数
14. /*************************************************************************
15. 函数功能:   对传入的数据进行一次快速排序（分成大于基准值和小于基准值的两部分）；
16. 输入参数:   待排序的数组，需要排序的下标范围（左端下标、右端下标）;
17. 返回值：    基准所在的下标
18. *************************************************************************/
19. /*
20. 思路：
21. 选定一个基准(默认左端):   用变量temp记录基准值;
23. loop:
24. 此时左端所在下标low代表的值可以被覆盖(值已经被复制了)
25. 从右端向左端的方向,开始与temp比较,直到遇到比temp小的数,(否则就high--左移),将这个小于temp的数(下标可假定为high')放到左边，左边下标low所在的数据上
27. 此时右端所在下标high代表的值可以被覆盖(值已经复制到下标low代表的值内了)
28. 从左端向左端的方向,开始与temp比较,直到遇到比temp大的数,(否则就low++后移),将这个大于temp的数(下标可假定为low')放到右边，左边下标high所在的数据上
30. 此时左端low'下标的数据可以被覆盖，回到loop;
32. 循环结束条件:low'后移high'前移 直到相遇，说明以基准值temp将这批数据分成两份完毕。
34. 注意：此时大小两份虽然分类完成，但是 作为基准值的数据 还未找到位置；【基准值应该放在下标为low的位置】
36. 看下面图理解
37. 注意，此时应low==high并且理应必须low==high，
38. 注意，此时下标所在位置的数据应该被覆盖，
39. 故基准值应该放在下标为low的位置(或者下标为high，反正两值相等)
40. *********************************************************
41. 《基准值临界情形图》
42. 基准值5
43. x x x x 6 3 x x x
44.         l h     此时基准值正在与l所代表元素比较l向右移中（说明h位置是无用数据）
45. x x x x 6 6 x x x
46.         l h     l数据复制给h,轮到下标h向左移动
47. x x x x 6 6 x x x
48.         ↑       两下标重合相等，此时应该放入基准值temp(h现在是无用数据)(low左边比基准值小，high右边比基准值大)
49. 基准值7
50. x x x x 6 5 x x
51.         l h     此时基准值正在与l所代表元素比较h向左移动中（说明l位置是无用数据）
52. x x x x 5 5 x x
53.         l h     h数据复制给l,轮到下标l向左移动(h现在是无用数据)
54. x x x x 5 5 x x
55.           ↑     两下标重合相等，此时应该放入基准值temp(h现在是无用数据)(low左边比基准值小，high右边比基准值大)
56. *********************************************************
57. */
59. int part(int arr[],int low,int high)
60. {
61.     //检查输入范围是否合法
62.     if(low>high)
63.     {
64.         return -1;
65.     }
66.     //选定一个基准值(以左端作为基准值)
67.     int temp=arr[low];//注意:下标low所在数据被temp保存
69.     //结束循环的条件
70.     while(low<high)
71.     {
72.         //比较右端,比基准大的仍然放在右边，不用管，继续向前判断下一个:故high--;
73.         while(temp<arr[high]&&low<high)
74.         {
75.             high--;//下标向前移动，判断下一个
76.         }
77.         //条件不满足时出循环，将这个小数据放到左边，下标为low的地方(low数据已经被保存)
78.         arr[low]=arr[high];
80.         //开始比较左端:比基准小得仍然放左边，继续向后判断下一个
81.         while(temp>arr[low]&&low<high)
82.         {
83.             low++;
84.         }
85.         //条件不满足，跳出循环，将这个小数据放到左边
86.         arr[high]=arr[low];//此时high所在数据，之前已经被放到循环前的low里了
88.         /*
89.         注意:这里内层循环增设了条件为low<high,
90.         图形解释:   见最下方《基准值临界情形图》PRO
91.         文字解释:
92.             当low与high相差为1时，假定low与low将值给high，开始判断high,
93.             此时high的值必定会满足，所以high会左移
94.             high移动到low的位置，仍然会满足值的条件条件
95.             high继续移动到low的左边，此时high值不满足条件；出循环并且交换数据；回到大循环，判断low<high
96.         */
97.     }
98.     //运行到此，说明low==high;
99.     arr[high]=temp;
100.     return high;//基准所在下标low或者high都可以
101. }
103. void quick_sort(int arr[],int low,int high)
104. {
105.     if(low>=high)
106.     {
107.         return;
108.     }
109.     int mid=part(arr,low,high);
110.     quick_sort(arr,low,mid-1);
111.     quick_sort(arr,mid+1,high);
112. }
114. int main()
115. {
116.     int arr[]={82,15,49,85,28,43,39,17,47,48};
117.     int len=sizeof(arr)/sizeof(arr[0]);
118.     printf("len=%d\n",len);
119.     //快速排序
120.     quick_sort(arr,0,9);
121.     //数据显示
122.     showData(arr,len);
123. }
125. /*
126. *********************************************************
127. 《基准值临界情形图》PRO     临界情形分析
128. 基准值5
129. x x x x 6 3 x x x
130.         l h     此时基准值正在与l所代表元素比较l向右移中（说明h位置是无用数据）
131. x x x x 6 6 x x x
132.         l h     l数据复制给h,轮到下标h向左移动
133. x x x x 6 6 x x x
134.         ↑       两下标重合相等，此时应该放入基准值temp(h现在是无用数据)
135. x x x x 6 6 x x x
136.       h l       内层循环不加low<high;则h会一直移动！直到小于基准值，才回到外层循环判断low<high
137. 基准值7
138. x x x x 6 5 x x
139.         l h     此时基准值正在与l所代表元素比较h向左移动中（说明l位置是无用数据）
140. x x x x 5 5 x x
141.         l h     h数据复制给l,轮到下标l向左移动(h现在是无用数据)
142. x x x x 5 5 x x
143.           ↑     两下标重合相等，此时应该放入基准值temp(h现在是无用数据)
144. x x x x 5 5 x x
145.           h l   内层循环不加low<high;则l会一直移动！直到大于基准值，才回到外层循环判断low<high
146. *********************************************************
147. */

复制代码

直接插入排序

1. //直接插入排序
2. void insert_sort(int arr[],int len)
3. {
4.     for(int i=1;i<len;i++)//
5.     {
6.         int temp=arr[i];//选定第i个，进行插入
7.         int j;
8.         for(j=i-1;j>=0&&arr[j]>temp;j--)//将在"我"之前的数据，依次向后搬运，直到遇到第一个比自己小的元素
9.         {
10.             arr[j+1]=arr[j];
11.         }
12.         arr[j+1]=temp;//插入位置！注意执行了"j--"才出的循环
13.     }
14. }

复制代码

改良版冒泡排序

1. //改良版冒泡排序
2. void bubble_sort(int buf[],int len)
3. {
4.     int temp;
5.     int flag=1;
6.     for(int i=0;i<len&&flag;i++)//轮数
7.     {
8.         flag=0;//使用标志位前，标志位初始值
9.         for(int j=0;j<len-1-i;j++)//每轮比较次数
10.         {
11.             if(buf[j]>buf[j+1])
12.             {
13.                 flag=1;//发生交换，标志位置1
14.                 temp=buf[j+1];
15.                 buf[j+1]=buf[j];
16.                 buf[j]=temp;
17.             }
18.         }
19.         //一轮下来没有发生交换，排序已完成，跳出循环
20.     }
21. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。