排序算法

Author Avatar
stormjie 9月 29, 2018
  • 在其它设备中阅读本文章

上篇提过我这几天在看数构,今天就来整理下排序算法,打算先更简单选择排序、冒泡排序、直接插入排序、折半插入排序、快速排序、归并排序,emmm以后可能会补更希尔排序和堆排序,看心情啦。

一、简单选择排序

基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换,然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止,简单选择排序是不稳定排序 。(太简单了,不具体说了)

public static void SelectSort(int[] numbers) {
    //数组长度
    int size = numbers.length; 
    int temp = 0;
    for(int i=0;i<size-1;i++) {
        //待确定的位置
        int min = i;
        //选择出应该在第i个位置的数
        for(int j=i+1;j<size;j++) 
            if(numbers[j] < numbers[min])
                min = j;
        //进行交换,如果min发生变化,则进行交换
        if (min != i) {
            temp = numbers[i];
            numbers[i] = numbers[min];
            numbers[min] = temp;
        }
    }
}

简单选择排序的比较次数与序列的初始排序无关。假设待排序的序列有n个元素,则比较次数总是n(n-1)/2。

而移动次数与序列的初始排序有关。当序列正序时,移动次数最少,为 0。

当序列反序时,移动次数最多,为3n(n-1)/2。

所以,综合以上,简单排序的时间复杂度为O(n2)

二、冒泡排序

基本思想:在要排序的一组数中,对相邻的元素进行两两比较,顺序相反则进行交换,这样,每一趟会将最小或最大的元素“浮”到顶端,最终达到完全有序,冒泡排序是稳定排序 。

public static void BubbleSort(int[] numbers) {
    boolean flag = true;
    int temp = 0;
    int i,j;
    for(i=0;i<numbers.length-1&&flag;i++) {
        //如果本轮没有进入if判断语句的执行语句,标志位flag为false
        flag = false;
        for(j=0;j<numbers.length-i-1;j++)
            if(numbers[j] > numbers[j+1]) {
                temp = numbers[j];
                numbers[j] = numbers[j+1];
                numbers[j+1] = temp;
                flag = true;
            }
    }
}

若记录序列的初始状态为正序,则冒泡排序过程只需进行一趟排序,在排序过程中只需进行n-1次比较,且不移动记录。

反之,若记录序列的初始状态为逆序,则需进行n(n-1)/2次比较和记录移动。

因此冒泡排序总的时间复杂度为O(n2)

三、直接插入排序

基本思想:每步将一个待排序的记录,按其顺序码大小插入到前面已经排序的字序列的合适位置(从后向前找到合适位置后),直到全部插入排序完为止,直接插入排序是稳定排序 。

public static void InsertSort(int[] numbers) {
    int size = numbers.length;
    int i,j;
    for(i=1;i<size;i++) {
        int temp = numbers[i];
        //假如temp比前面的值小,则将前面的值后移
        for(j=i-1;j>=0&&temp<numbers[j];j--)
            numbers[j+1] = numbers[j];
        numbers[j+1] = temp;
    }
}

当数据正序时,执行效率最好,每次插入都不用移动前面的元素,时间复杂度为O(n)

当数据反序时,执行效率最差,每次插入都要前面的元素后移,时间复杂度为O(n2)

所以,数据越接近正序,直接插入排序的算法性能越好

四、折半插入排序

基本思想:折半插入排序是对直接插入排序的改进,排序原理同直接插入排序,是稳定的排序算法。

与直接插入排序的区别在于:在寻找待排序数据的正确位置时,使用了二分查找。

public static void BinarySort(int[] numbers) {
    int i,j;
    int low,high,mid;
    int temp;
    for(i=1;i<numbers.length;i++) {
        temp = numbers[i];
        low = 0;
        high = i - 1;
        //寻找插入点
        while(low <= high) {
            mid = low + (high - low) / 2;
            if(temp < numbers[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        //移动有序序列中插入点之后的元素
        for(j=i-1;j>=high+1;j--)
            numbers[j+1] = numbers[j];
        //将待排序数据插入有序数列
        numbers[high+1] = temp;
    }
}

折半插入排序只是减少了比较次数,但是元素的移动次数不变。折半插入排序平均时间复杂度为O(n2)

五、快速排序

基本思想:选择一个关键值作为基准值。比基准值小的都在左边序列(一般是无序的),比基准值大的都在右边(一般是无序的)。一般选择序列的第一个元素。

一次循环:从后往前比较,用基准值和最后一个值比较,如果比基准值小的交换位置,如果没有继续比较下一个,直到找到第一个比基准值小的值才交换。找到这个值之后,又从前往后开始比较,如果有比基准值大的,交换位置,如果没有继续比较下一个,直到找到第一个比基准值大的值才交换。直到从前往后的比较索引等于从后往前比较的索引,结束第一次循环,此时,对于基准值来说,左右两边就是有序的了。

接着分别比较左右两边的序列,重复上述的循环。

在快速排序中,相等元素可能会因为分区而交换顺序,所以它是不稳定的算法。

public static void QuickSort(int[] numbers,int low,int hight) {
        //如果左边索引大于等于右边,说明该组序列整理完毕
        if(low >= hight) 
            return;
        int i = low;
        int j = hight;
        //用子表的第一个记录做基准
        int k = numbers[i]; 
        //本轮排序开始,当i==j时本轮排序结束,将基准赋值给numbers[i]
        while (i < j) { 
            //从表的两端交替向中间扫描
            while(i < j && numbers[j] >= k)
                j--;
            numbers[i] = numbers[j];
            while(i < j && numbers[i] < k)
                i++;
            numbers[j] = numbers[i];
        }
        //将基准数值替换回numbers[i]
        numbers[i] = k;

        //对低子表进行递归排序
        QuickSort(numbers,low,i-1);
        //对高子表进行递归排序
        QuickSort(numbers,i+1,hight); 
} 

当数据有序时,以第一个关键字为基准分为两个子序列,前一个子序列为空,此时执行效率最差。

而当数据随机分布时,以第一个关键字为基准分为两个子序列,两个子序列的元素个数接近相等,此时执行效率最好。

所以,数据越随机分布时,快速排序性能越好;数据越接近有序,快速排序性能越差。

快速排序平均时间复杂度也为O(nlogn),最好情形下快速排序空间复杂度大约为O(logn)。

六、归并排序

基本思想:归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起,即分而治之)。

public static void MergeSort(int[] numbers,int start,int end) {
    if(start >= end)
        return;

    int mid = (start + end) >> 1;
    // 递归实现归并排序
    MergeSort(numbers,start,mid);
    MergeSort(numbers,mid+1,end);
    merge(numbers,start,mid,end);
}

//将两个有序序列归并为一个有序序列(二路归并)
public static void merge(int[] numbers,int start,int mid,int end) {

    //定义一个临时数组,用来存储排序后的结果
    int[] temp = new int[end+1];
    //临时数组的索引
    int tempStart = start;
    int low = start;
    //第二个序列的起始下标
    int center = mid + 1;
    //取出最小值放入临时数组中
    while(start <= mid && center <= end)
        temp[low++] = numbers[start] > numbers[center] ? numbers[center++] : numbers[start++];

    //若还有段序列不为空,则将其加入临时数组末尾
    while(start <= mid)
        temp[low++] = numbers[start++];
    while(center <= end)
        temp[low++] = numbers[center++];

    //将临时数组中的值copy到原数组中
    for(int i=tempStart;i<=end;i++)
        numbers[i] = temp[i];
}

归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。值得一提的是,Java中Arrays.sort()采用了一种名为TimSort的排序算法,就是归并排序的优化版本。每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。

总的平均时间复杂度为O(nlogn)。而且,归并排序不管最好或者最坏的情况下平均时间复杂度均为O(nlogn)

七、总结

各种排序的稳定性,时间复杂度、空间复杂度、稳定性总结如下图: