排序学习笔记

排序和查找：

排序：
排序sorting是把一系列类似的数据按升序或降序排列的过程。C标准库提供的qsort函数，直接排序。
排序算法分为：随机存取目标排序法；顺序目标排序法。

排序算法的分类：
对数组的排序：①交换排序 exchange
②选择排序 selection
③插入排序 insertion

排序算法的评价：
平均情况下对信息排序的速度。
最优和最劣情况下的速度。

冒泡法：
bubble sort。最著名的排序方法，其出名在于名字形象且操作简单，其名声不好在于它是目前最差的排序之一。
冒泡排序法，是一种交换排序，涉及重复比较和必要时相邻元素的交换。气泡排序法，通过双重循环驱动完成。外层循环使数组被扫描count-1次，由此确保最劣时函数退出后，各元素都在正确位置上。内部循环实施比较和交
初始： d c a b
第一轮： a d c b
第二轮： a b d c
第三轮： a b c d

 1 void BubbleSort(int *arr)
 2 {
 3     int i, j;
 4     int temp;
 5 
 6     for (i = 0; i < N; i++)
 7     {
 8         for (j = i + 1; j < N - 1; j++)
 9         {
10             if (arr[i] > arr[j])
11             {
12                 temp = arr[i];
13                 arr[i] = arr[j];
14                 arr[j] = temp;
15             }
16         }
17     }
18     return ;
19 }

稍作改进的冒泡排序：

 1 void Bubble(int *arr)
 2 {
 3     int i, j, temp;
 4     int flag;
 5 
 6     for (i = N - 1; i > 0; i--)
 7     {
 8         flag = 0;
 9         for (j = 0; j < i; j++)
10         {
11             if (arr[j] > arr[j + 1])
12             {
13                 temp = arr[j];
14                 arr[j] = arr[j + 1];
15                 arr[j + 1] = temp;
16                 flag = 1;
17             }
18         }
19         if (0 == flag)
20             break;
21     }
22     return ;
23 }

冒泡排序法优化版--抖动排序（shaker sort）：
在大值一侧失序的元素（如 dcab中的a）一遍就到达正确位置；在小值一侧失序的元素(如 dcab中的d)，则需多遍才能升到恰当位置。我们可以对数组的各次扫描交替改变方向，从而使严重失序的元素快速进至正确的位置。

选择排序：
选择排序中，先选择最小元素并将其与第一个元素交换，然后，在剩余n-1个元素中选择最小者并与第2个元素交换，如此推进到最后两个元素。
初始： d c a b
第一轮： a c d b
第二轮： a b d c
第三轮： a b c d

插入排序：
先对数组的前两个元素排序，然后，把第3个元素按序插入已排好的前两个元素中。随后，把第4个元素插入正排序的三元素表中。
初始： d c a b
第一轮： a d c b
第二轮： a b d c
第三轮： a b c d

改进的排序：
冒泡排序和选择排序，执行时间是n平方级的。
谢尔排序shell sort 和快速排序quick sort。

谢尔排序：
谢尔排序的操作方法常常用叠海贝seashell的原理来描述。一般排序方法是从插入排序导出并基于增量减少原则。谢尔排序首先对间隔N个位置的元素排序，然后，在对N-1个位置的元素排序，直到，对相邻元素排序。谢尔排序时高效的，每遍都提高了有序性。
增量的准确序列可以变化，唯一规则是最后增量必须为1.

快速排序：
quick sort。快速排序的基本思想是分区partition。实际上，快速排序的最清晰实现就是递归算法。一般过程是先选一个称为比较数的值，然后把数组分为两段。大于或等于分区值的元素都放在一边，小于分区的元素放在另一边。然后对数组的另一段重复上述过程，直到该数组完成排序。

初始： f e d a c b
第一遍：b c a d e f 对bca和def

 1 void quick(int s[], int low, int high)
 2 {
 3     int key, i, j;
 4     i = low;    
 5     j = high;    
 6     key = s[i];    
 7     while(i < j)    
 8     {        
 9         while(i<j && s[j]>=key)    
10             j--;    
11         if(i<j)
12             s[i] = s[j];    
13         while(i<j && s[i]<=key) 
14             i++;
15         if(i<j)    
16             s[j] = s[i];        
17     }    
18     s[i] = key;//i==j即key值所应该放的位置
19    if(i-1 > low)    
20         quick(s, low, i-1);//左边至少2个元素
21    if(i+1 < high)    
22         quick(s, i+1, high);//右边至少2个元素
23    
24     return ;
25 }