首页 > 程序开发 > 软件开发 > 其他 >

[数据结构] 九大基础排序总结与对比

2016-06-08

稳定性:稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的,当有两个相等键值的纪录R和S,且在原本的列表中R出现在S之前,在排序过的列表中R也将会是在S之前。

1、对比分析图

均按从小到大排列

k代表数值中的”数位”个数

n代表数据规模

m代表数据的最大值减最小值 

稳定性:稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的,当有两个相等键值的纪录R和S,且在原本的列表中R出现在S之前,在排序过的列表中R也将会是在S之前。

 由于九个排序算法写在一篇博客里太多了,所以我把它们分开进行了详细的阐述,分别是:冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、桶排序、基数排序

2、补充

2.1 快排的partition函数

  作用:给定一个数组arr[]和数组中任意一个元素a,重排数组使得a左边都小于它,右边都不小于它。

// A[]为数组,start、end分别为数组第一个元素和最后一个元素的索引
 // povitIndex为数组中任意选中的数的索引
static int partition(int A[], int start, int end, int pivotIndex){
    int i = start, j = end, pivot = A[pivotIndex];
    swap(A[end], A[pivotIndex]);
    while(i < j){
        while(i < j && A[i] <= pivot) ++i;
        while(i < j && A[j] >= pivot) --j;
        if(i < j) swap(A[i], A[j]);
    }
    swap(A[end], A[i]);
    return i;
}

2.2 冒泡排序的改进

思路:

①、加一个标志位,当某一趟冒泡排序没有元素交换时,则冒泡结束,元素已经有序,可以有效的减少冒泡次数。

  /** 
     * 引入标志位,默认为true 
     * 如果前后数据进行了交换,则为true,否则为false。如果没有数据交换,则排序完成。 
     */  
    public static int[] bubbleSort(int[] arr){  
        boolean flag = true;  
        int n = arr.length;  
        while(flag){  
            flag = false;  
            for(int j=0;jarr[j+1]){  
                    //数据交换  
                    int temp = arr[j];  
                    arr[j] = arr[j+1];  
                    arr[j+1] = temp;  
                    //设置标志位  
                    flag = true;  
                }  
            }  
            n--;  
        }  
        return arr;  
    }  

②、记录每一次元素交换的位置,当元素交换的位置在第0个元素时,则排序结束。

2.3快排优化

① 快速排序在处理小规模数据时的表现不好,这个时候可以改用插入排序。

②对于一个每个元素都完全相同的一个序列来讲,快速排序也会退化到 O(n^2)。要将这种情况避免到,可以这样做:

在分区的时候,将序列分为 3 堆,一堆小于中轴元素,一堆等于中轴元素,一堆大于中轴元素,下次递归调用快速排序的时候,只需对小于和大于中轴元素的两堆数据进行排序,中间等于中轴元素的一堆已经放好。

相关文章
最新文章
热点推荐