常用的排序算法

 2016-05-07 17:24:24     算法   1051


导读: 在日常工作中,虽然很少用到排序算法,但是,掌握一些常用的排序算法却是不可缺少的。尤其是一些公司的面试题,会经常提到这个。最近在一次面试过程中,就问到了相关问题,借此机会做一些整理,也好加深一些理解和记忆。

排序算法汇总


以下为排序算法汇总表:

算法分类 算法名称
交换排序 冒泡排序 鸡尾酒排序 奇偶排序 梳排序 侏儒排序 快速排序 臭皮匠排序 Bogo排序
插入排序 插入排序 希尔排序 伸展排序 二叉查找树排序 图书馆排序 耐心排序
归并排序 归并排序 梯级归并排序 振荡归并排序 多相归并排序 串列排序
分布排序 珠排序 桶排序 爆炸排序 计数排序 鸽巢排序 相邻图排序 基数排序 闪电排序 插值排序
并发排序 双调排序器 Batcher归并网络 两两排序网络
混合排序 区块排序 Tim排序 内省排序 Spread排序 J排序
其他 拓扑排序 煎饼排序 意粉排序

复杂度和稳定性如图:

排序算法

以上好多排序算法名称都没有听说过,更别提用到了。只整理了几个常用的。

交换排序


交换排序主要有冒泡排序和快速排序。我们这里主要讨论快速排序。

快速排序是对冒泡排序的一种改进。使用分治法策略来把一个序列分为两个子序列。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

算法描述:

  • 1、从数列中挑出一个元素,称为"基准"
  • 2、重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区操作
  • 3、递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序

实现过程图:

快速排序

步骤描述图:

快速排序

Java代码

基础类

public class BaseSort {
    /**
     * 数组打印
     * @param x
     */
    public static void print(int[] x) {
        int l = x.length - 1;
        for (int i = 0; i <= l; i++) {
            System.out.printf((i == 0) ? ("[%d") : ((i == l) ? (", %d]\n") : (", %d")), x[i]);
        }
    }

    /**
     * 数组元素交换
     */
    public static void swap(int[] x, int a, int b) {
        int t = x[a];
        x[a] = x[b];
        x[b] = t;
    }

    /**
     * 采用二分法查找法,找出数组中比指定数字要小的索引位置
     * @param a
     * @param fromIndex
     * @param toIndex
     * @param key
     * @return
     */
    public static int binarySearch(int[] a, int fromIndex, int toIndex, int key) {
        int mid;
        while (fromIndex <= toIndex) {
            mid = (fromIndex + toIndex) >>> 1;
            if (a[mid] > key) {
                toIndex = mid - 1;
            } else {
                fromIndex = fromIndex + 1;
            }
        }
        return fromIndex;
    }
}

快速排序类

public class QuickSort extends BaseSort {

    public static void main(String[] args) {
        int[] x = {23, 34, 1, 22, 82, 3, 9, 10, 41, 37};
        print(x);
        quickSort(x);
        print(x);
    }

    public static void quickSort(int[] arr) {
        //swap(arr, 0, arr.length / 2); //如果开始以中间数为基准数,只需将中间的这个数和第一个数交换即可
        qsort(arr, 0, arr.length - 1);
    }

    /**
     * 递归调用左侧排序和右侧排序
     *
     * @param arr
     * @param low
     * @param high
     */
    private static void qsort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);
            qsort(arr, low, pivot - 1);
            qsort(arr, pivot + 1, high);
        }
    }

    /**
     * 找出基准数的索引位置
     * @param arr
     * @param low
     * @param high
     * @return
     */
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[low]; //基准数
        while (low < high) {
            while (low < high && arr[high] >= pivot) // 从右向左找第一个小于pivot的数
                --high;
            if(low < high) {
                arr[low] = arr[high];
                low++;
            }

            while (low < high && arr[low] <= pivot)  // 从左向右找第一个大于pivot的数
                ++low;
            if (low < high) {
                arr[high] = arr[low];
                high--;
            }
        }
        arr[low] = pivot;
        return low;
    }
}

说明

  • 快速排序是二叉查找树(二叉查找树)的一个空间最优化版本。不是循序地把数据项插入到一个明确的树中,而是由快速排序组织这些数据项到一个由递归调用所隐含的树中。这两个算法完全地产生相同的比较次数,但是顺序不同。对于排序算法的稳定性指标,原地分区版本的快速排序算法是不稳定的。其他变种是可以通过牺牲性能和空间来维护稳定性的

  • 快速排序的最直接竞争者是堆排序(Heapsort)。堆排序通常比快速排序稍微慢,但是最坏情况的运行时间总是O(n log n)。快速排序是经常比较快,除了introsort变化版本外,仍然有最坏情况性能的机会。如果事先知道堆排序将会是需要使用的,那么直接地使用堆排序比等待introsort再切换到它还要快。堆排序也拥有重要的特点,仅使用固定额外的空间(堆排序是原地排序),而即使是最佳的快速排序变化版本也需要Θ(log n)的空间。然而,堆排序需要有效率的随机存取才能变成可行

  • 快速排序也与归并排序(Mergesort)竞争,这是另外一种递归排序算法,但有坏情况O(n log n)运行时间的优势。不像快速排序或堆排序,归并排序是一个稳定排序,且可以轻易地被采用在链表(linked list)和存储在慢速访问媒体上像是磁盘存储或网络连接存储的非常巨大数列。尽管快速排序可以被重新改写使用在炼串列上,但是它通常会因为无法随机存取而导致差的基准选择。归并排序的主要缺点,是在最佳情况下需要Ω(n)额外的空间

插入排序


每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。

插入排序又分直接插入排序和折半插入排序(二分插入排序)。

算法描述:

  • 1、从第一个元素开始,该元素可以认为已经被排序
  • 2、取出下一个元素,在已经排序的元素序列中从后向前扫描
  • 3、如果该元素(已排序)大于新元素,将该元素移到下一位置
  • 4、重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  • 5、将新元素插入到该位置后
  • 6、重复步骤2~5

过程图:
插入排序

Java代码

public class InsertionSort extends BaseSort {

    public static void main(String[] args) {
        int[] x = {23, 34, 1, 22, 82, 3, 9, 10, 41, 37};
        //straight(x);
        shell(x);
        print(x);
    }

    /**
     * 直接插入排序
     * 数列分有序和无序两部分,当无序元素小于有序的最后一个元素时,才会移动元素,找到合适位置插入
     * 插入排序要优于冒泡排序,因为冒泡排序的元素比较次数大于插入排序
     *
     * @param arr
     */
    public static void straight(int[] arr) {
        for (int i = 0; i < arr.length; i++)
            for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--)
                swap(arr, j, j - 1);
    }

    /**
     * 二分查找法插入排序
     *
     * @param arr
     */
    public static void binary(int[] arr) {
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            int temp = arr[i];
            if (arr[i - 1] > temp) {
                int insertIndex = binarySearch(arr, 0, i - 1, temp);//采用二分查找算法
                for (int j = i; j > insertIndex; j--) {
                    arr[j] = arr[j - 1];
                }
                arr[insertIndex] = temp;
            }
        }
    }
}

希尔排序


也称递减增量排序算法,是插入排序的一种更高效的改进版本。是非稳定排序算法。

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

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
  • 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位

希尔排序图

Java代码

/**
 * 希尔排序(分组插入排序)
 *
 * @param arr
 */
public static void shell(int[] arr) {
    int i, j, gap, len = arr.length;
    for (gap = len / 2; gap > 0; gap /= 2)
        for (i = gap; i < len; i++)
            for (j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j -= gap)
                swap(arr, j, j + gap);
}

说明

  • 直接插入排序:如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数减去(n-1)次。平均来说插入排序算法复杂度为O(n2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择

  • 二分查找法排序:与直接插入排序相比,有一定几率减少元素的比较次数,一般情况下,效率比直接插入排序的要高

  • 希尔排序:步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序,最终算法以步长为1进行排序。当步长为1时,算法变为插入排序,这就保证了数据一定会被排序

归并排序


归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

算法描述

  • 1、申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
  • 2、设定两个指针,最初位置分别为两个已经排序序列的起始位置;
  • 3、比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
  • 4、重复步骤3直到某一指针超出序列尾;
  • 5、将另一序列剩下的所有元素直接复制到合并序列尾。

过程图:
归并排序图

Java代码

public class MergeSort extends BaseSort {
    public static void main(String[] args) {
        int[] x = {23, 34, 1, 22, 82, 3, 9, 10, 41, 37};
        mergeSort(x);
        print(x);
    }

    /**
     * 归并排序算法
     * @param arr
     */
    public static void mergeSort(int[] arr) {
        int l = arr.length;
        int[] temp = new int[l]; //临时数组
        recMergeSort(arr, temp, 0, l - 1);
    }

    /**
     * 递归分割数据到只剩两个元素
     *
     * @param arr
     * @param temp
     * @param low
     * @param high
     */
    private static void recMergeSort(int[] arr, int[] temp, int low, int high) {
        if (low == high) {
            return;
        } else {
            int mid = (low + high) / 2;
            recMergeSort(arr, temp, low, mid);
            recMergeSort(arr, temp, mid + 1, high);
            merge(arr, temp, low, mid + 1, high);
        }
    }

    /**
     * 归并操作,将两两元素归并成整个有序的数组
     *
     * @param arr
     * @param temp
     * @param left
     * @param right
     * @param last
     */
    private static void merge(int[] arr, int[] temp, int left, int right, int last) {
        int j = 0;
        int lowIndex = left;
        int mid = right - 1;
        int n = last - lowIndex + 1;
        while (left <= mid && right <= last) {
            if (arr[left] < arr[right]) {
                temp[j++] = arr[left++];
            } else {
                temp[j++] = arr[right++];
            }
        }
        while (left <= mid) {
            temp[j++] = arr[left++];
        }
        while (right <= last) {
            temp[j++] = arr[right++];
        }
        for (j = 0; j < n; j++) {
            arr[lowIndex + j] = temp[j];
        }
    }
}

说明

  • 归并排序是稳定的排序.即相等的元素的顺序不会改变。

  • 速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列。


参考: