几种常见的排序算法

常见的排序算法有冒泡排序，简单选择排序，直接插入排序，快速排序，归并排序，堆排序，桶排序等，这篇文章中我们主要分析前五种排序，包括它们的实现，稳定性分析，时间复杂度分析以及空间复杂度分析。

以下都假设给定一个长度为n的数组
1，冒泡排序
在冒泡排序中， 我们从数组的开始进行比较，如果第一个元素大于第二个元素，我们就将两个元素互换，接下来我们比较第二个元素和第三个元素，如果第二个元素大于第三个元素我们就把它们交换，以此类推，每次循环都得到一个最大的数。代码如下：

public void bubblesort(int[] array){
	for(int i=0;i<array.length-1;i++)
		for(int j=0;j<array.length-i-1;j++){
			if(array[j]>array[j+1]){
				int tem=array[j];
				array[j]=array[j+1];
				array[j+1]=tem;
		      }
	}
}

一共循环了(n-1) + (n-2) +(n-3) .....+1次，时间复杂度为O(n^2)。我们仅用了一个变量tem来保存要交换的数据，因此空间复杂度时O(1)。每次比较时两个元素如果相等两个元素的相对位置不变，因此冒泡排序是稳定的。

2，简单选择排序
简单选择排序和冒泡排序看上去真好相反，冒泡排序的每个循环都会找到一个最大数放在数组的后面，而简单选择排序每次都确定一个最小的元素放在最前面。代码如下：

public void selectsort(int[] array){
	for(int i=0;i<array.length-1;i++)
		for(int j=i+1;j<array.length;j++){
			if(array[i]>array[j]){
				int tem=array[i];
				array[i]=array[j];
				array[j]=tem;
			}
	}
}

和冒泡排序一样一共循环了(n-1) + (n-2) +(n-3) + .....+1次，所以时间复杂度同样为O(n^2)。我们仅用了一个变量tem来保存要交换的数据，因此空间复杂度为O(1)。因为在选择较小元素时，相同元素的相对位置可能发生变化，比如{2，2，1} 第一个2会和1交换位置，因此简单选择排序是不稳定排序。

3，直接插入排序
直接插入排序是每次从右边的无序序列中选择一个元素，插入多左边有序序列的合适位置，过程是从右往左进行的。代码如下：

public void insertsort(int[] array){
	for(int i=1;i<array.length;i++)
		for(int j=i;j>0;j--){
			if(array[j-1]>array[j]){
				int tem=array[j-1];
				array[j-1]=array[j];
				array[j]=tem;
			}
        }
}

整个过程循环了1 + 2 + 3 +...+(n-1) 次，所以时间复杂度为O(n^2)。我们仅用了一个变量tem来保存要交换的数据，因此空间复杂度为O(1)。因为每次循环我们都是通过从后向前遍历已排序序列,然后插入,此时相等元素依然可以保持原有位置，因此直接插入排序时稳定排序。如果从左往右遍历有序序列，就和选择排序一样，变成一个不稳定排序。我们在实现的时候尽量把算法设计成稳定排序。

前面的三种排序时间复杂度都是O(n^2), 在实际应用中效率不高，下面的这两种排序算法，大大地提高了排序的效率，也是我们解题中经常用到的排序算法。

4，快速排序
在快速排序中，我们随机选择一个元素，然后把数组分为两段，左边的元素都小于这个元素，右边的元素都大于这个元素，然后用同样的方法处理左边的序列和右边的序列，知道整个数组变为有序。我们从代码来分析，代码如下：

public void quick_sort(int s[], int l, int r)  {  
    if (l < r) {   
        int i = l, j = r, pivot = s[l];  
        while (i < j) {  
            while(i < j && s[j] >= pivot) 
                j--;    
            if(i < j)   
                s[i++] = s[j];  
              
            while(i < j && s[i] < pivot) 
                i++;    
            if(i < j)   
                s[j--] = s[i];  
        }  
        s[i] = pivot;  
        quick_sort(s, l, i - 1); 
        quick_sort(s, i + 1, r);  
    }  
}

在平均情况下，快速排序要递归log(n)次，每次都要处理n个元素，所以时间复杂度时O(nlogn)。因为要递归log(n)次，所以要用log(n)的栈来实现递归，所以空间复杂度为O(log n)。在极端的情况下，快排的时间复杂度是O(n^2)，例如如果数组本身时倒序的，每次取最小，这样的时间复杂度就是O(n^2),一共循环了(n-1) + (n-2) +(n-3) + .....+1次。在排序过程中，相同大小的元素的相对位置会发生变化，例如{2，2，1}在一次排序后第一个2会和1交换位置，因此快速排序是一个不稳定排序。

5，归并排序
归并排序是采用了分治的思想，每次把数组分成两段，直到子序列的长度为1，每个子序列都是有序的，然后再合并这些有序的子序列，直到整个序列都有序。我们从代码来分析它的时间复杂度以及空间复杂度，代码如下：
//通过递归使每个子序列都有序，然后再将它们合并

public void mergesort(int low,int high)
	{
		if(low<high)
		{
			int middle=low+(high-low)/2;
		    mergesort(low,middle);
		    mergesort(middle+1,high);
		    mergepart(low,middle,high);
		}
	}
    
public void mergepart(int low, int middle, int high)
	{
		for(int i=low;i<=high;i++)
		{
			temparray[i]=array[i];
		}
		int i=low;
		int j=middle+1;
		int k=low;
		
		while(i<=middle&&j<=high){
			if(temparray[i]<=temparray[j]){
				array[k]=temparray[i];
				i++;
			}else{
				array[k]=temparray[j];
				j++;
			}
				k++;
		}
		while(i<=middle){
			array[k]=temparray[i];
			i++;
			k++;
		}
		while(j<=high){
			array[k]=temparray[j];
			j++;
			k++;
		}
	}
}

程序执行过程中，总共递归了log(n)次，每次都要处理n个数据，所以它的时间复杂度为O(nlogn)，因为每次都是把子序列分为长度相等的两段，因此它的最坏情况和平均情况的时间复杂度都是O(nlogn)。对于空间复杂度，不同的算法实现空间复杂度也不同。在这个代码实现中，我们用了一个长度为n的辅助数组，每次都把较小的元素放入数组中，最后我们把剩余的元素也放入目标数组中。递归调用了log(n)次，加上我们开辟的长度为n的数组，所以它的空间复杂度为O(n)。对于稳定性，当有序列的左右两子序列合并的时候一般是先遍历左序列,所以左右序列如果有相等元素,处在左边的仍然在前,因此归并排序时稳定的排序.

总结：
冒泡排序： 时间复杂度O(n^2)，空间复杂度O(1)，稳定排序
简单选择排序： 时间复杂度O(n^2)，空间复杂度O(1)，不稳定排序
快速插入排序：时间复杂度O(n^2)，空间复杂度O(1)，稳定排序
快速排序：时间复杂度O(nlogn) 平均情况，O(n^2)最坏情况，空间复杂度O(logn)，不稳定排序
归并排序：时间复杂度O(nlogn)，空间复杂度要根据算法具体实现来确定，稳定排序