排序

几种慢速排序方法

冒泡排序

冒泡排序的思想主要是交换排序

**基本思想:**两两比较相邻记录的关键字,如果反序就交换,直到没有反序的记录为止

**时间复杂度:**O(n²) 最小值n-1次查找 最大值n(n-1)/2次查找且做等量级移动

简单选择排序

简单选择排序(Smple Selection Sort)就是通过n-i次关键字间的比较,从n-i+1个记录中选择出关键词最小的记录,并和第i个记录进行交换 ( 1<= i <=n )

**时间复杂度:**O(n²),

比较次数恒定为n(n-1)/2

交换次数最小为0，最大为n-1

复杂度相对于冒泡排序略低

直接插入排序

直接插入排序就是将一个记录插入已经排好序的有序表中,从而得到一个新的、记录数＋1的有序表

时间复杂度：O(n²)

平均的比较和移动次数为n²/2，性能高于直接插入和冒泡

希尔排序

先简单介绍下基本有序：最小的关键词基本在前面，不大不小的基本在中间，最大的基本在后面

因此我们采用跳跃分割的策略：将相距某个增量的记录组成一个子序列，在子序列进行插入排序后就是基本有序，使得排序效率提高。

性能主要取决于增量的值，研究指出为dlta[k]=2^t-k+1-1（0<=k<=t<=log₂(n+1)）时效率较高,时间复杂度：O(n^3/2)

堆积法

堆是具有下列性质的完全二叉树

• 每个结点的值都大于或者等于其左右孩子结点的值，成为大顶堆
• 每个结点的值都小于或者等于其左右孩子结点的值，成为小顶堆

堆排序算法

以大顶堆为例子

• 将待排序数组构成一个大顶堆，将顶端结点和堆数组末尾互换
• 将剩余的n-1个序列重新构成一个大顶堆，得到n-1中的次大值
• 重复上述

问题在于大顶堆的构建和剩余元素重构大顶堆

具体算法略过，讨论一下算法的复杂度

• 堆构建的时间复杂度复杂度为：O（n）

• 单次重构的时间复杂度为：O（logi），堆顶获取n-1次。

  总体花费：O（nlogn）

综上堆排序时间为O（nlogn）

总结

堆排序空间占用较高，但是排序依旧不够稳定（记录的跳跃性），不适合待排序序列较少的情况

归并排序

2路归并排序的原理是

• 假设初始序列有n个记录，则可以看成是n个有序的子序列，每个子序列长度为1
• 然后两两归并，得到 n/2 个长度为2 或者为 1 的有序子序列
• 重复两两并归

复杂度分析

时间复杂度：O（nlogn）

空间复杂度：O（n+logn） 递归情况

​ O（n） 非递归情况 因此最好使用非递归算法

属于比较占用内存但是效率高且稳定的算法

快速排序

快速排序属于从冒泡排序进阶而来

快速排序的思想：

通过一趟排序将待排记录分割为两部分，一部分的关键字比另一部分小，将这两部分记录继续进行排序。

具体实现

public class QuickSort2 {
        //三个水桶原理，进行数据的交换
       private void swap(int[] arr,int i ,int j ){
           int temp = arr[i];
           arr[i] = arr[j];
           arr[j] = temp;
       }

       public void quickSort(int[] arr,int start,int end ){
            if(start >= end)
                return;
            int k = (arr[start] + arr[start/2 + end/2] + arr[end])/3;
            int i = start,j = end;
            while (i != j){
                while (i < j && arr[j]>=k)
                    j--;
                swap(arr,i,j);
                while (i < j && arr[i]<=k)
                    i++;
                swap(arr,i,j);
       }
            quickSort(arr,start,i-1);
            quickSort(arr,i+1,end);

    }
    public static void main(String[] args) {
        int[] arr = {5, 2, 6, 9, 1, 3, 4, 8, 1, 10,};
        new QuickSort().quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

算法复杂度

时间复杂度:

最好的情况 O（n）

最坏的情况 O（n²）

平均时间复杂度为 O（nlog₂n）

优化

• 将快速排序的递归实施尾递归优化
• 优化选取中间值的方法(三数取中、九数取中)

int k = (arr[start] + arr[start/2 + end/2] + arr[end])/3;

• 小数组是，high或者low的值小于7（也有资料显示50），使用直接插入求解
• 优化不必要的交换