排序算法总结

作者: 火乐君_52cd | 来源:发表于2018-07-19 14:02 被阅读0次

基础排序算法

基础排序算法相关接口和实现类

接口：

import com.sun.javafx.css.Combinator;

interface Sortable{
    boolean less(Comparable x,Comparable v);
    void exchange(Comparable[] a,int i,int j);
    void show(Comparable[] a);
}

实现类（后续排序的父类）：

public class Sort implements Sortable{
    public void exchange(Comparable[] a,int i,int j){
        Comparable k = a[i];
        a[i] = a[j];
        a[j] = k;
    }
    public boolean less(Comparable x,Comparable v){
        return x.compareTo(v) < 0;
    }
    public void show(Comparable[] a){
        for(int i = 0;i < a.length;i++){
            System.out.println(a[i]);
        }
    }
}

1.选择排序

两层循环：
1. 内层循环进行比较，从而找出输入序列中的最小值（或最大值）
2. 外层循环负责交换，将最小值（或最大值）与输入序列的第一个元素进行交换
时间复杂度：
1. 内层循环总的时间复杂度为n*(n+1)/2，在较大输入长度时可理解为o(n²/2)。
2. 外层循环每次只进行一次交换，故而与输入序列长度呈线性关系，时间复杂度为o(n)。
缺点：
选择排序的时间复杂度只与输入序列长度有关，故其对有序序列及随机序列的排序时间相同。
优点：
选择排序具有最小的移动次数，其移动次数最大为输入序列长度n，故而与输入序列长度成完全线性关系。
代码实现如下：

public class SelectionSort{
    public void sort(Comparable[] a){
        int n = a.length;
        for(int i = 0;i < n;i++){
            int minindex = i;
            for(int j = i;j < n;j++){
                if(less(a[j],a[minindex])){
                    minindex = j;
                }
            }
            exchange(a, i, minindex);
        }
    }
    public void exchange(Comparable[] a,int i,int j){
        Comparable k = a[i];
        a[i] = a[j];
        a[j] = k;
    }
    public boolean less(Comparable x,Comparable v){
        return x.compareTo(v) < 0;
    }
    public static void main(String[] args){
        String[] a = args;
        SelectionSort s = new SelectionSort();
        s.sort(a);
        for(int i = 0;i < a.length;i++){
            System.out.println(a[i]);
        }
    }
}

2. 插入排序

当前位置左侧的数组为有序数组（和选择排序相同），但其位置状态可能因后续插入内容发生改变（和选择排序不同）
插入排序的时间复杂度与输入序列的初始顺序有关
时间复杂度：
1. 最优情况：
  时间复杂度为o(n-1)，进行N-1次比较，0次交换，输入序列为排好序的状态。
2. 最差情况：
  时间复杂度为o(n²)，进行n²/2次比较及n²/2次交换，输入序列为所求顺序的倒序。
3. 平均时间复杂度：
  时间复杂度为o(n²/2)，进行n²/4次比较和n²/4次交换，输入序列顺序随机。
适用情况：
1. 每一个元素与其最终位置相差不远的序列
2. 一个小序列加入到一个大的有序序列中
3. 一个序列中仅有小部分元素不在其最终位置

public class InsertionSort extends Sort{//定义一个Sort类，内部实现了Sortable接口的less()，exchange()，show()三个方法
    public void sort(Comparable[] a){//定义一个sort方法，内部调用Sort类中的三个方法，从小到大排序
        for(int i = 1;i < a.length;i++){//输入序列中待比较的元素
            for(int j = i - 1;j >= 0;j--){//与已经从小到大排好序的序列进行比较，寻找插入位置，也可以用while循环来写,不过需要判断循环终止条件和其位置
                if(less(a[j+1], a[j])){
                    exchange(a, j, j+1);
                }
            }
        }
        show(a);
    }
    public static void main(String[] args){
        //可用于字符串的排序
        InsertionSort i = new InsertionSort();//这个排序方法不能对两位数进行排序。。。,只排第一位的数字。。。
        String[] s = args;
        i.sort(s);
    }
}

3.希尔排序

基本思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少, 组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

排序思路
1. 根据输入序列的长度选择初始增量h
2. 对原序列每h位取其元素，生成h个h-sorted子序列
3. 对每个子序列进行插入排序，从子序列第二位元素开始向前比较
4. 这些子序列之间是相互交叉的，且希尔排序并不会额外占用空间进行存储

希尔排序示意图如下：

image.png
希尔排序代码如下：

public class ShellSort extends Sort{
    public void sort(Comparable[] a){
        int N = a.length;
        int h = 1;
        while(h < N/3) h = 3*h + 1;//计算初始增量，设置为小于序列长度的1/3
        while(h >= 1){
            //每一个子序列视为一个插入排序的输入序列，插入排序是从输入序列的第二个元素开始
            for(int i = h;i < N;i++){
                //每h个元素选出一个加到子序列中，
                //所以原序列中的第一个元素在子序列中的下一个元素为第1+h个。
                for(int j = i;j >= h && less(a[j],a[j-h]);j = j - h){
                    exchange(a, j, j - h);
                }
            }
            System.out.println("h = " + h);
            h = h/3;//增量逐渐衰减到0，插入排序从初始排h个序列到最后合并成一个序列
            show(a);
        }
    }
    public static void main(String[] args){
        ShellSort s = new ShellSort();
        s.sort(args);
    }
}

高级排序算法

1.归并排序算法（merge-sort）

1.1 Top-Down MergeSort

时间复杂度为N*lg(N)
基本思想：

将待排序的输入序列拆分成两个子序列

递归的对两个子序列进行归并排序

将排序完成的结果合并

书中将归并排序分成了两个部分：

abstract in-place mergeSort：（这个是merge部分，即合并部分）

操作于两个已经排序完成但互不相连的序列合并的一种算法

将输入的两个有序序列复制，生成一份拷贝。index:low,mid,high分别对应着两个序列的头和尾。左序列头为low,尾为mid。

单层循环，循环遍历原始序列，用于将重排后的结果输入。内部用if-else语句比较拷贝序列从头部开始的元素的大小，并依从小到大的顺序作为结果添加到原始序列中，完成排序。

top-down mergeSort：（基于合并部分与拆分部分相结合的总过程）

将输入序列迭代拆分至长度为一

迭代合并拆分后的单元，长度如1,2,4，直至回归原始序列

合并过程中采用第一部分即merge部分的思想

降低归并排序的时间复杂度：

使用插入排序降低复杂度：
在较小序列（length <= 15）中使用插入排序(推荐使用)，选择排序等简单排序方法可降低mergeSort的时间复杂度（10-15%）。
检测序列是否已经有序：
比较a[mid]和a[mid + 1]的大小，从而减少merge()的调用，直接将两子序列连接即可。

归并排序算法代码实现：

public class MergeSort extends Sort{
    private Comparable[] a;
    public void mergeSort(Comparable[] a){//一个对外的方法，隐藏内部具体实现
        mergeSort(a,0,a.length - 1);
        show(a);
    }
    public void mergeSort(Comparable[] a,int l,int r){//迭代的拆分步骤
        if(l >= r){
            return;
        }
        int mid = l + (r - l)/2;//取得输入数组的中间index
        //不过我其实没想通为什么他们不直接写成（l + r）/2
        mergeSort(a,l,mid);
        mergeSort(a,mid + 1,r);
        merge(a,l,mid,r);//在完成所有拆分之后开始迭代的合并
    }
    public void merge(Comparable[] a,int l,int mid,int r){//合并步骤
        /*这里，算法和算法导论两本书实现方法有很大的区别
        算法导论在这里通过新建两个新数组，分别存储原始数组中的a[l...mid],a[mid+1...r]
        所以在存放时为使其有序，需在末端人工添加一个最大值
        算法则将原始数组进行了一次拷贝，通过对对应index上拷贝数组值的比较，进行排序并放回原始数组
        */
        //我个人更倾向于算法书中的思想，更清晰，也许是因为实现算法所用的语言不同的原因。
        Comparable[] a_copy = new Comparable[a.length];
        for(int k = l;k <= r;k++){//生成一个待合并数组的拷贝
            a_copy[k] = a[k];
        }
        int i = l;
        int j = mid + 1;
        for(int k = l;k <= r;k++){//基于拷贝数组比较的重排过程
            if(i > mid) a[k] = a_copy[j++];
            else if(j > r) a[k] = a_copy[i++];
            else if(less(a_copy[j], a_copy[i])) a[k] = a_copy[j++];
            else a[k] = a_copy[i++];
        }
    }
    public static void main(String[] args){
        MergeSort m1 = new MergeSort();
        m1.mergeSort(args);
    }
}

1.2 Bottom-Up MergeSort（个人比较喜欢这个～）

基本思想：

构建一个merge，从最小的子序列开始，迭代的执行合并操作
子序列的长度为1,2,4,8...最后一个子序列可能不是等长的，因为原始序列数组长度不定
每次合并之后序列的size都为上一次的两倍

代码实现：

/*
这里遵循的是书上写的自底向上的思想
从最小的子序列开始合并，逐步生成并合并更高一级的子序列
较之自顶向下的归并排序
减去了切割序列的步骤
从而节省时间（我猜的！！！）
*/

public class Bottom_Up_MergeSort extends Sort{
    //private Comparable[] a;
    public void mergeSort(Comparable[] a){
        int N = a.length;
        for(int size = 1;size < N;size += size){
            for(int l = 0;l < N;l = l + 2*size){
                merge(a, l, l + size - 1, Math.min(l + 2*size - 1, N - 1));
            }
        }
        show(a);
    }
    public void merge(Comparable[] a,int l,int mid,int r){//合并步骤
        /*这里，算法和算法导论两本书实现方法有很大的区别
        算法导论在这里通过新建两个新数组，分别存储原始数组中的a[l...mid],a[mid+1...r]
        所以在存放时为使其有序，需在末端人工添加一个最大值
        算法则将原始数组进行了一次拷贝，通过对对应index上拷贝数组值的比较，进行排序并放回原始数组
        */
        //我个人更倾向于算法书中的思想，更清晰，也许是因为实现算法所用的语言不同的原因。
        Comparable[] a_copy = new Comparable[a.length];
        for(int k = l;k <= r;k++){//生成一个待合并数组的拷贝
            a_copy[k] = a[k];
        }
        int i = l;
        int j = mid + 1;
        for(int k = l;k <= r;k++){//基于拷贝数组比较的重排过程
            if(i > mid) a[k] = a_copy[j++];
            else if(j > r) a[k] = a_copy[i++];
            else if(less(a_copy[j], a_copy[i])) a[k] = a_copy[j++];
            else a[k] = a_copy[i++];
        }
    }
    public static void main(String[] args){
        Bottom_Up_MergeSort b1 = new Bottom_Up_MergeSort();
        b1.mergeSort(args);
    }
}

2.快速排序算法（queckSort）

原址排序算法
平均时间复杂度为o(Nlg(N))
最差情况时间复杂度为o(N²)
是归并排序的完善版本：
1. 归并排序：将输入序列分成两个子序列，将子序列排序后，进行比较后合并成一个序列
2. 快速排序：当划分后的子序列有序时，划分元素左子序列最大值小于划分元素，右子序列最小值大于划分元素
基本思想：
1. 选中输入序列中某一元素作为划分元素，将输入序列划分为两个子序列
2. 遍历输入序列，将比划分元素小的序列移入左子序列，比划分元素大的序列移入右子序列
3. 将划分元素与左子序列中最后一个元素交换位置
4. 将子序列作为输入序列，选中子序列中某一元素作为划分元素，再次划分成两个子序列
5. 重复以上步骤
代码实现：

public class QuickSort extends Sort{
    public void quicksort(Comparable[] a){//隐藏内部实现的接口
        quicksort(a,0,a.length - 1);//调用具体实现的方法
        show(a);
    }
    private void quicksort(Comparable[] a,int left,int right) {
        /*总输入数组a
        原址排序算法，即排序不消耗额外的物理内存，在输入序列地址上直接进行排序
        待排序序列左右两端的索引left,right*/
        if(right <= left) return;//保证输入序列存在
        int j = partition(a,left,right);//核心方法
        //递归调用quicksort方法以切割数组
        quicksort(a,left,j);
        quicksort(a,j+1,right);
    }
    private int partition(Comparable[] a,int left,int right){
        /*包含有一个双层的嵌套循环
        外层循环持续执行直到左右索引相遇，即保证a[j]处于其最终位置
        a[j]左侧所有元素皆不大于a[j],a[j]右侧所有元素皆不小于a[j]
        */
        Comparable v = a[left];//定义划分元素
        int i = left;
        int j = right + 1;
        while(true){
            while(less(a[++i],v)) if(i >= right) break;//扫描整个数组，找出比v大的元素
            while(less(v,a[--j])) if(j <= left) break;//扫描整个数组，找出比v小的元素
            if(i >= j) break;
            exchange(a,i,j);
        }
        exchange(a,left,j);//最后，将v与a[j]交换，放到其合适位置上，划分左小右大的数组
        return j;//返回的是划分点，该位置元素已处于最终位置
    }
    public static void main(String[] args){
        QuickSort q = new QuickSort();
        q.quicksort(args);
    }
}

快速排序算法优化方法

利用插入排序进行优化：
当子序列小于特定阈值时，用插入排序替换快速排序，剩余部分序列直接进行插入排序而不再做切割处理
去三个元素求平均值作划分元素：
从序列中选择三个元素，取中位数，以这个中位数作为划分元素将输入序列划分成子序列
熵最优排序（我觉得最牛皮）：
主要优化队列中相同元素较多时的算法时间损耗，算法一书介绍了一种三分法的直观优化方法

三分法优化快速排序

算法思想：
将输入序列通过5个索引值划分成三个区域（key<partition,key=partition,key>partition）

具体结构：

设置索引lo,lt,i,gt,hi

a[lo , lt - 1]为值小于partition的部分，a[lt,i-1]为值等于partition的部分，a[i,gt-1]为待比较的部分，a[gt,hi]为值大于partition的部分

实现步骤：

lt = lo,gt = hi

a[i] < v: exchange(a[lt++],a[i++])

a[i] > v: exchange(a[i++],a[gt--])

a[i] = v: i++

代码实现：

排序算法总结

基础排序算法

基础排序算法相关接口和实现类

1.选择排序

2. 插入排序

3.希尔排序

高级排序算法

1.归并排序算法（merge-sort）

1.1 Top-Down MergeSort

降低归并排序的时间复杂度：

1.2 Bottom-Up MergeSort（个人比较喜欢这个～）

2.快速排序算法（queckSort）

快速排序算法优化方法

三分法优化快速排序

3. 优先队列（最大堆/最小堆实现）

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读