排序算法

_{参考文档《十大经典排序算法》}

排序算法内容会在之后学期开设的《数据结构》课程中有更深入的介绍。本文档仅给出简单的介绍，若需做详细了解也可见参考网页。在本课程中基本不对算法效率有要求，只需完成指定编程任务，但在实际工程中往往需要使用高效稳定的算法进行开发，因此建议同学们在接触编程时先对最基本的各种排序算法有感性的认识。本文共介绍四种排序算法：选择、冒泡、插入、快速排序。其他涉及到使用数据结构的排序如堆排序将会在后续课程中介绍。（而且一定会要求熟练掌握…）

一、选择排序

选择排序是一种简单直观的排序算法，其想法就是不断循环搜索找到序列中最大（或最小）值，进行选择排序，算法基本步骤为：

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
重复前两步至所有元素完成排序

int main(){
    int lh, rh, k, tmp;
	int array[] = {2, 5, 1, 9, 10, 0, 4, 8, 7, 6};
	for (lh = 0; lh < 10; lh++){ 
		rh = lh;
		for (k = lh; k < 10; ++k)
			if ( array[k] < array[rh] ) rh = k;
		tmp = array[lh]; 
		array[lh] = array[rh];
		array[rh] = tmp;
	}
	for (lh =0; lh<10; ++lh) cout << array[lh] << ' ';
	return 0;
}

二、冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。

其算法步骤为

比较相邻的元素。如果第一个比第二个大，就交换他们两个
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。（这步做完后，最后的元素会是最大的数）
针对所有的元素重复以上的步骤，除了最后一个，直到没有任何一对数字需要比较

int main(){
	int a[] = { 0, 3, 5, 1, 8, 7, 9, 4, 2, 10, 6};
	int i, j, tmp, n = 11;
	bool flag;
	for (i=1; i<n; ++i) { //控制循环次数
		flag = false;
		for (j=0; j<n-i; ++j) // 最后i个已经排好
			if (a[j+1] < a[j]){
				tmp = a[j]; a[j] = a[j+1]; 
				a[j+1] = tmp; 
				flag = true;
			}
		if (!flag) break;/* 一趟冒泡中没有发生交换，排序结束*/
	}

	for (i=0; i<n; ++i) cout << a[i] << ' ';
	return 0;
} 

三、插入排序

除了前两种课程中提到的的排序方法，还有多种序列排序算法，这里再介绍插入排序以及快速排序。

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。算法步骤为：

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

int main(){
	int array[]={ 0, 3, 5, 1, 8, 7, 9, 4, 2, 10, 6};
    int n = 11;
    for(int i = 1;i < n;i++){
        int temp = array[i];
        for(int j = i - 1;j >= 0;j--){
            if(array[j] > temp){
                array[j + 1] = array[j];
                array[j] = temp;
            }
            else
                break;
        }
    }
    
    for (i=0; i<n; ++i) cout << a[i] << ' ';
	return 0;
}

四、快速排序

从命名就可以看出快速排序算法在效率上是很高的，平均情况下只需Ο(nlogn) 次比较即可完成序列排序，最坏情况则需要Ο(n²)次。快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。快速排序是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。其基本步骤为

从数列中挑出一个元素，称为 “基准”（pivot）
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序

示例代码使用了函数的概念，可在学到函数章后重新回看此程序。

Paritition1(int A[], int low, int high) {		//分区函数
   int pivot = A[low];
   while (low < high) {
     while (low < high && A[high] >= pivot) {
       --high;
     }
     A[low] = A[high];
     while (low < high && A[low] <= pivot) {
       ++low;
     }
     A[high] = A[low];
   }
   A[low] = pivot;
   return low;
 }

void QuickSort(int A[], int low, int high) //快排母函数
 {
   if (low < high) {
     int pivot = Paritition1(A, low, high);
     QuickSort(A, low, pivot - 1);
     QuickSort(A, pivot + 1, high);
   }
 }