冒泡排序Bubble Sort

    冒泡排序是一种交换排序，排序的方法很简单：反复扫描待排序记录，在扫描的过程中比较相邻元素的大小，如果逆序则交换位置，直到没有反序为止。

    例如有一组无序数组 a[0]、a[1]、...a[n-1] n个数，用冒泡排序对它进行升序排序。首先比较 a[0] 和 a[1] 的值，如果 a[0] 大于 a[1] 则交换位置，否则不变，再比较 a[1] 和 a[2] 的值，若 a[1] 大于 a[2] 则交换位置，否则不变，以此类推...在这个过程中不断地将两个相邻元素中较大的那个往后移动，最后必然将待排序的记录序列中最大的关键字换到了待排序记录序列的末尾。然后进行第二趟排序，对前 n-1 个记录进行同样的操作......冒泡排序最多进行 n-1 趟。

    如：对 3  2  7  6  5 进行升序排序。

冒泡排序过程：

第一趟：

    2  3  7  6  5

    2  3  7  6  5

    2  3  6  7  5

    2  3  6  5  7

第二趟：

    2  3  6  5  7

    2  3  6  5  7

    2  3  5  6  7

第三趟：

    2  3  5  6  7

    2  3  5  6  7

第四趟：

    2  3  5  6  7

C源代码：

void BubbleSort(int a[],int n)
{
	int i,j,tmp;
	for(i=0; i<n; i++){
		for(j=0; j<n-i-1; j++){
			if(a[j] > a[j+1]){
				tmp = a[j];
				a[j] = a[j+1];
				a[j+1] = tmp;
			}
		}
	} 
}

java源代码：

public static void BubbleSort(int[] a,int n){
	int i=0,j=0;
	//for(i=0; i<n; i++){
	while(i<n){
		for(j=0; j<n-i-1; j++){
			if(a[j] > a[j+1]){
				int tmp = a[j];
				a[j] = a[j+1];
				a[j+1] = tmp;
			}
		}
		i++;
	}
}

    冒泡排序时间复杂度为 O(n^2)，空间复杂度为 O(1)。

    冒泡排序还可以优化一下：若某一趟冒泡排序过程中，没有发生过交换，则可以直接结束整个排序过程。

源代码：

void BubbleSort(int a[],int n)
{
	int i,j,tmp,flag = 1;
	for(i=0; i<n && flag; i++){
		flag = 0;
		for(j=0; j<n-i-1; j++){
			if(a[j] > a[j+1]){
				tmp = a[j];
				a[j] = a[j+1];
				a[j+1] = tmp;
				flag = 1; //若有数据交换，置为1 
			}
		}
	} 
}

快速排序QuickSort

    快速排序是冒泡排序的改进。基本思想：通过一趟快速排序，在待排序序列中选取一个关键字K，然后将所有比它小的数放在它前面，所有比它大的数放在它后面。这样一趟快速排序就把待排序的数分割成了独立两部分。然后按照相同的方法对其中一部分进行快速排序，直到每一部分的长度不超过 1 为止。快速排序不是一种稳定的排序算法。而冒泡排序是一种稳定的排序算法。

快速排序算法：

    取第一个数作为基准，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。而寻找结束的条件就是，1）找到一个小于或者大于 key 的数（大于或小于取决于你想升序还是降序）；2）没有符合条件1的，并且i与j的大小没有反转。

一趟快速排序的算法：

1）设置两个变量 i  j，排序开始：i=0  j=n-1；

2）以第一个元素作为基准，key = a[0];

3）从 j 开始向前搜索，找到第一个小于 key 的值 a[j]，将 a[j] 和 a[i] 互换；

4）从 i  开始向后搜索，找到第一个大于 key 的值 a[i]，将 a[i] 和 a[j] 互换；

5）重复步骤3、4，直到 i=j。

    时间复杂度为O(nlog2n)（n 倍的以 2 为底 n 的对数）。空间复杂度O(log2n)（以 2 为底 n 的对数）。

源代码C：

void QuicklySort(int *a,int low,int high)
{
	if(low >= high)	return ;
	int i = low, j = high;
	int key = a[low];	//选一个基准 
	while(i < j)
	{
		while(i<j && key <= a[j]){
			j--;	//向前寻找 
		}
		a[i] = a[j]; //找到后把它赋给前面被拿走的i的值 
		while(i<j && key >= a[i]){
			i++;
		}
		a[j] = a[i];
	}
	a[i] = key;//找完一遍后把中间数key回归 
	QuicklySort(a,low,i-1);
	QuicklySort(a,i+1,high);
} 

源代码java：

public static void QuicklySort(int[] a,int low,int high){
	if(low > high)	return ;
	int key = a[low];
	int i = low, j = high;
	while(i < j){
		while(i<j && a[j]>=key){
			j--;
		}
		a[i] = a[j];
		while(i<j &&  a[i]<=key){
			i++;
		}
		a[j] = a[i];
	}
	a[i] = key;
	QuicklySort(a,low,i-1);
	QuicklySort(a,i+1,high);
}