常见排序算法的总结与比较

1 冒泡排序

/*
作者：chenguolin
功能：测试冒泡排序的效率
日期：2013.01.10 22:01
*/
/*
1 冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。
即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。
至此第一趟结束，将最大的数放到了最后。
在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，
大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。
如此下去，重复以上过程，直至最终完成排序。

2 由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。

3 冒泡排序的时间复杂度为O(n^2)，是一个稳定的排序算法
*/

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<ctime>
using namespace std;

const int MAXN = 100;
int arr[MAXN];

//冒泡排序主体
void bubbleSort(){
	for(int i = 0 ; i < MAXN-1 ; i++){
		for(int j = 0 ; j < MAXN-1-i ; j++){
		   if(arr[j] > arr[j+1])
			  swap(arr[j] , arr[j+1]);
		}
	}
}

//输出测试是否排序正确
void output(){
   for(int i = 0 ; i < MAXN ; i++)
	  cout<<arr[i]<<" ";
   cout<<endl;
}

int main(){
	//首先产生随机100000个数
    srand(time(0));
	for(int i = 0 ; i < MAXN ; i++){
	   int tmp = rand();
	   arr[i] = tmp;
	}

	clock_t star , end;
	star = clock();//开始测试
	bubbleSort();
	end = clock();//结束测试
	cout<<"Run time = "<<(end - star)<<endl;//输出几ms
	output();
	return 0;
}

2 插入排序

/*
作者：chenguolin
功能：测试插入排序的时间
日期：2013.01.10 22:33
*/

/*
1 假定这个数组的序是排好的，然后从头往后，如果有数比当前外层元素的值大，则将这个数的位置往后挪，直到当前外层元素的值大于或等于它前面的位置为止.
  这具算法在排完前k个数之后，可以保证a[1…k]是局部有序的，保证了插入过程的正确性.

2 插入排序的时间复杂度为O(n^2)，是一个稳定的算法。
*/


#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<ctime>
using namespace std;

const int MAXN = 100000;
int arr[MAXN];

//直接插入排序的主体
void insertSort(){
	for(int i = 1 ; i < MAXN ; i++){
		int tmp = arr[i];
		int j;
		for(j = i-1 ; j >= 0 ; j--){
			if(arr[j] > tmp)//只要比tmp大就往后移动一位
			  arr[j+1] = arr[j];
			else
			  break;
		}
		arr[j+1] = tmp;//j+1这位插入tmp
	}
}

//输出测试是否正确
void output(){
	for(int i = 0 ; i < MAXN ; i++)
	    cout<<arr[i]<<" ";
	cout<<endl;
}

int main(){
	srand(time(0));
	for(int i = 0 ; i < MAXN ; i++){
	   int tmp = rand();
	   arr[i] = tmp;
	}
	clock_t star , end;
	star = clock();
	insertSort();
	end = clock();
	cout<<"Run time = "<<(end-star)<<" ms"<<endl;
	output();
	return 0;
}

3 选择排序

/*
作者：chenguolin
功能：测试选择排序的时间效率
日期：2013.01.10  23:03
*/

/*
1 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 

2 选择排序的时间复杂度O(n^2) , 是不稳定的排序方法。
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<algorithm>
using namespace std;

const int MAXN = 100000;
int arr[MAXN];

//选择排序的主体
void selectSort(){
	for(int i = 0 ; i < MAXN-1 ; i++){
		int pos = i;
		for(int j = i+1 ; j < MAXN ; j++){
			if(arr[j] < arr[pos])
		       pos = j;
		}
		swap(arr[pos] , arr[i]);
	}
}

//输出测试数据是否排序正确
void output(){
	for(int i = 0 ; i < MAXN ; i++)
	    cout<<arr[i]<<" ";
	cout<<endl;
}

int main(){
   srand(time(0));
   for(int i = 0 ; i < MAXN ; i++){
       int tmp = rand();  
       arr[i] = tmp;
   }
   clock_t star , end;
   star = clock();
   selectSort();
   end = clock();
   cout<<"Run time = "<<(end-star)<<" ms"<<endl;
   output();
   return 0;
}

4 快速排序

/*
作者：chenguolin
功能：测试快速排序的时间效率
日期：2013.01.10 23:45
*/

/*
1 它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
  然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 

2 快速排序是随机算法中平均最快的，时间复杂度为O(nLogn)，有可能退化成O(n^2)。是一个不稳定的算法

int partition(int *arr, int l, int r){
	int pos = (l+r)>>1;//选择中间的数作为基准
	swap(arr[pos], arr[r]);//把这个数交换到最后一个位置
	int leftSeqNum = l; //左子序列的结束位置

	for(int i = l; i < r; i++){
		if(arr[i] < arr[r]){
		   if(leftSeqNum < i)
			   swap(arr[leftSeqNum], arr[i]);
		   leftSeqNum++;
		}	
	}
	//再把基准的值交换到正确的位置
	swap(arr[leftSeqNum], arr[r]);
	return leftSeqNum;
}
void quickSort(int *arr, int l, int r){
    if(arr == NULL || l == r)
		return;
	int index = partition(arr, l, r);
	if(l < index)
		quickSort(arr, l, index-1);
	if(index < r)
		quickSort(arr, index+1, r);
}

5 归并排序

/*
作者：chenguolin
功能：测试归并排序的时间效率
日期：2013.01.11 0:00
*/

/*
1 归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，
  每个子序列是有序的。然后再把有序子序列合并为整体有序序列
2 归并排序是一个不存在最好.最坏的情况的算法，算法的时间复杂度为O(nLogn)。是一个稳定的算法
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<algorithm>
using namespace std;

const int MAXN = 100000;
int arr[MAXN];
int tmpArr[MAXN];

//合并
void merge(int left , int mid , int right){
	int i , j , pos;
	i = left , j = mid+1 , pos = left;
	while(i <= mid && j <= right){
	     if(arr[i] <= arr[j])
			tmpArr[pos++] = arr[i++];
		 else
			tmpArr[pos++] = arr[j++];
	}
	while(i <= mid)
	     tmpArr[pos++] = arr[i++];
	while(j <= right)
	     tmpArr[pos++] = arr[j++];
    for(i = left ; i <= right ; i++)
	    arr[i] = tmpArr[i];
}

//两路-归并排序的主体
void mergeSort(int left , int right){
	if(left < right){
	   int mid = (left+right)>>1;
	   mergeSort(left , mid);
	   mergeSort(mid+1 , right);
	   merge(left , mid , right);//合并两部分
	}
}

//测试输出的数据是否正确
void output(){
    for(int i = 0 ; i < MAXN ; i++)
		cout<<arr[i]<<" ";
	cout<<endl;
}

int main(){
	srand(time(0));
	for(int i = 0 ; i < MAXN ; i++){
	    int tmp = rand();
		arr[i] = tmp;
	} 
	clock_t star , end;
	star = clock();
	mergeSort(0 , MAXN-1);
	end = clock();
	cout<<"Run time = "<<(end-star)<<" ms"<<endl;
	output();
	getchar();
	return 0;
}

/*
Author: chenguolin
Date: 2014-02-24
*/

const int MAXN = 1010;
const int INF = 1<<30;

void merge(int *arr, int left, int mid, int right){
    int tmpLeft[MAXN];
    int tmpRight[MAXN]; 
    //copy to tmp arr
    for(int i = 1, j = left; i <= (mid-left+1); i++, j++)
        tmpLeft[i] = arr[j];
    for(int i = 1, j = mid+1; i <= (right-mid); i++, j++)
        tmpRight[i] = arr[j];
    tmpLeft[mid-left+1] = INF;
    tmpRight[right-mid] = INF;
    //merge two arr
    int l = 1, r = 1;
    for(int i = left; i <= right ; i++){
        if(tmpLeft[l] < tmpRight[r])
            arr[i] = tmpLeft[l++];
        else
            arr[i] = tmpRight[r++];
    }
}

void merge_sort(int *arr, int left, int right){
    if(left < right){
        int mid = (left+right)>>1;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }
}

int main(){
    return 0;
}

6 堆排序

/*
作者：chenguolin
功能：测试堆排序的时间效率
日期：2013.01.11 0:57
*/

/*
1 堆是一棵完全二叉树
2 堆排序首先是先把一个无序的序列整成一个最大堆，然后利用每次取出堆的“根节点+调整堆为最大堆”这种思路对一个序列排序
3 一个具有n个元素的数组，利用堆排序需要总共需要n次调整（第一次是调整为最大堆+排序的n-1调整）
4 堆排序的时间复杂度为O(nLogn)，是一个不稳定的算法.
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<algorithm>
using namespace std;

const int MAXN = 100000+10;
const int N = MAXN-10;
int arr[MAXN];

//调整为最大堆
void adjustMaxHeap(int n , int size){
	int l_child , r_child , MAX;
	l_child = 2*n , r_child = 2*n+1 , MAX = n;
	if(l_child <= size && arr[l_child] > arr[MAX])
		MAX = l_child;
	if(r_child <= size && arr[r_child] > arr[MAX])
		MAX = r_child;
	if(MAX != n){//这里只有当MAX != n的时候才进行向下的调整，否则已经是最大或者到叶子节点不用调整
		swap(arr[n] , arr[MAX]);
	    adjustMaxHeap(MAX , size);
	}
}

//把无序序列建成一个最大堆
void initMaxHeap(){
    for(int i = N/2 ; i >= 1 ; i--)//从第一个非叶子节点n/2~1之间做n/2次调整
		adjustMaxHeap(i , N);
}

//堆排序
void heapSort(){
	int size = N;//size是实时的记录堆的元素个数
	for(int i = N ; i >= 2 ; i--){//如果是n个元素只要n-1次即可，当一个元素的时候就是最大不用做
	   swap(arr[i] , arr[1]);//把堆的根节点取出，把第i个元素换上去，这个时候size--就不会去调整到i了。
	   size--;
	   adjustMaxHeap(1 , size);//每次都要进行调整
	}
}

//测试输出数据是否正确
void output(){
	for(int i = 1 ; i <= N ; i++)
		cout<<arr[i]<<" ";
	cout<<endl;
}

int main(){
   srand(time(0));
   for(int i = 1 ; i <= N ; i++){
      int tmp = rand();
	  arr[i] = tmp;
   }
   clock_t star , end;
   star = clock();
   initMaxHeap();
   heapSort();
   end = clock();
   cout<<"Run time = "<<(end-star)<<" ms"<<endl;
   output();
   getchar();
   return 0;
}