[排序算法] 交换排序（2种）

1.冒泡排序

【思想】不停地比较相邻的记录，如果不满足排序要求就交换相邻数据，直到所有的记录都已经排好序

【特点】稳定

空间代价：O(1)

时间代价：O(n^2)

-比较次数　　　　　　　 -交换次数　

·最少：O(n)　　　　　　·最少：0

·最多：O(n^2)　　　　　·最多：O(n^2)

 1 void BubbleSort(int Array[], int n)
 2 {
 3     bool NoSwap;            // 是否发生了交换的标志
 4     int i, j;
 5     for(i = 0; i < n-1; i ++)
 6     {
 7         NoSwap = true;        // 标志初始为真
 8         for(j = n - 1; j > i; j --)
 9             if(Array[j] < Array[j-1])  // 判断是否逆置
10             {
11                 swap(Array[j], Array[j - 1]);    // 交换逆置对
12                 NoSwap = false;    // 发生了交换，标志变为假
13             }
14         if (NoSwap) return;        // 没发生交换，则排好序
15     }
16 }

2.快速排序

【思想】基于分治法的排序

·选择轴值（pivot）

·将序列划分为两个子序列L和R，使得L中的所有记录都小于或等于轴值，R中的记录都大于轴值

·对子序列L和R递归进行快速排序

【特点】不稳定

空间代价：O(logn)

时间代价：O(nlogn)

分治策略的基本思想：

-分 -- 划分子问题

-治 -- 求解子问题（子问题不重叠）

-合 -- 综合解

轴值选择：

·尽可能使L,R长度相等

·选择策略：

　-选择最左边记录（第一个记录）

-随机选择

-选择平均值

分割过程（整个快速排序的关键）：

·分割算法1

（1）备份轴值（首记录）

（2）取两个指针low和high，初始值就设为第二个元素和最后一个元素的下标，low <= high

（3）移动两个指针

　　·从high所指位置向左搜索，找到第一个比轴值小的元素

　　·从low所指位置向右搜索，找到第一个比轴值大的元素

（4）交换low和high两位置的值

（5）重复（3）、（4）两步骤的过程，直到low > high

（6）把轴放在high所指的位置

 1 int Partition1(int Array[], int first, int last)
 2 {
 3     int low = first + 1,high = last;
 4     int pivot = Array[first];
 5     while(low <= high)
 6     {
 7         while(low <= high && Array[low] <= pivot) low++;
 8         while(low <= high && Array[high] > pivot) high --;
 9         if(low < high)
10             swap(Array[high--] , Array[low++]);
11     }
12     swap(Array[first],Array[high]);
13     return high;
14 }
15 void QSort(int Array[], int first, int last)
16 {
17     if(first < last)
18     {
19         int x = Partition1(Array,first,last);
20         QSort(Array,first,x - 1);
21         QSort(Array,x + 1,last);
22     }
23 }

·分割算法2

（1）备份轴值（首记录）

（2）取两个指针low和high，初始值就是序列两端的下标，保证low <= high

（3）移动两个指针

　　·从high所指位置向左搜索，找到第一个比轴值小的元素，将其放在low的位置

　　·从low所指位置向右搜索，找到第一个比轴值大的元素，将其放在high的位置

（4）交换low和high两位置的值

（5）重复（3）、（4）两步骤的过程，直到low = high

（6）把轴放在low所指的位置

 1 int Partition2(int Array[], int first, int last)
 2 {
 3     int low = first, high = last;
 4     int pivot = Array[first];
 5     while(low < high)
 6     {
 7         while(low <= high && Array[high] >= pivot) high --;
 8         Array[low] = Array[high];
 9         while(low < high && Array[low] <= pivot) low ++;
10         Array[high] = Array[low];
11     }
12     Array[low] = pivot;
13     return low;
14 }
15 void QSort(int Array[], int first, int last)
16 {
17     if(first < last)
18     {
19         int x = Partition2(Array,first,last);
20         QSort(Array,first,x - 1);
21         QSort(Array,x + 1,last);
22     }
23 }