十三、查找和排序

---

 

---

1.排序

冒泡

、

两个两个比，大的往后排

插入

一个个往前插，然后保持有序，跟排手牌的方式差不多

选择

快速排序

先找到第一个元素的确切位置，劈成两半

h向左移，如果h的值比9小，则h的值赋给l，h停止，l开始

然后l的值比9小，则右移，如果发现有值比9大，则赋给h，l停止，h开始

最终9的位置定下来，左边是7、0、8、2，右边是13、10

算法演示

递归的终止条件是当下标low等于下标high

1. void QuickSort(int * a, int low, int high)

2. {

3. int pos;

4. if (low < high)

5. {

6. pos = FindPos(a, low, high);

7. QuickSort(a, low, pos - 1);

8. QuickSort(a, pos + 1, high);

9. }

10. }

只要下标low小于high，就不停地向中间靠拢

1. int FindPos(int * a, int low, int high)

2. {

3. int val = a[low];

4. while (low < high)

5. {

6. while (low < high && a[high] >= val)

7. –high;

8. a[low] = a[high];

9. while (low < high && a[low] <= val)

10. ++low;

11. a[high] = a[low];

12. }//终止while循环之后low和high一定是相等的

13. a[low] = val;

14. return low;

15. }

归并排序

先两个两个，然后四个四个，最后八个八个

2.查找

3.排序和查找的关系

排序时查找的前提

排序是重点