几种常见的排序算法


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

以下都假设给定一个长度为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),空间复杂度要根据算法具体实现来确定,稳定排序
本站声明
本文转载自:http://kickcode.iteye.com/blog/2260785     作者:KickCode     发布日期:2015-12-01     本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。


 
© 2014-2016 ITdaan.com 粤ICP备14056181号