logo头像
Snippet 博客主题

数据结构之排序

本文于486天之前发表,文中内容可能已经过时

数据结构和算法是整个计算机科学与技术领域永远逃避不了的话题,博主大学有过数据结构这门学科,不过特别后悔当时没有好好学习.仅学的那么点东西现在几乎忘得一干二净.虽说学的浅薄,但对整个编程思想还是很有帮助的.

十种常见排序算法

十种常见排序算法可分为两大类:

  • 非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序.
  • 线性时间非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此称为线性时间非比较类排序.

十大排序算法分类
十大排序算法复杂度

冒泡排序

冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名“冒泡排序”.

算法描述

  • 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
  • 针对所有的元素重复以上的步骤,除了最后一个;

    动图演示

    冒泡排序

    代码演示

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    /**
    *
    * 冒泡排序
    *
    * @author tong.li
    * @param arr = {6,3,8,2,9,1}
    *
    * 第0趟比较5次: 3,6,8,2,9,1 => 3,6,8,2,9,1 => 3,6,2,8,9,1 => 3,6,2,8,9,1 => 3,6,2,8,1,9
    * 第1趟比较4次: 3,6,2,8,1,9 => 3,2,6,8,1,9 => 3,2,6,8,1,9 => 3,2,6,1,8,9
    * 第2趟比较3次: 2,3,6,1,8,9 => 2,3,6,1,8,9 => 2,3,1,6,8,9
    * 第3趟比较2次: 2,3,1,6,8,9 => 2,1,3,6,8,9
    * 第4趟比较1次: 1,2,3,6,8,9
    */
    public static void bubbleSort(int ... arr) {
    if ( arr==null || arr.length <= 0) {
    return;
    }
    // 外循环控制趟数
    for (int i = 0; i < arr.length; i++) {
    // 内循环控制次数
    // for(int j=1;j<arr.length-i;j++){
    for (int j = 0; j < arr.length - 1 - i; j++) {
    //相邻两个元素进行比较
    if( arr[j] > arr[j + 1]) {
    // 采用异或方式进行变量互换
    arr[j] = arr[j] ^ arr[j + 1];
    arr[j + 1] = arr[j] ^ arr[j + 1];
    arr[j] = arr[j] ^ arr[j + 1];
    }
    }
    }
    }

快速排序(面试官最爱问的排序算法)

快速排序(Quicksort)是对冒泡排序的一种改进.
快速排序由C.A.R.Hoare在1962年提出.基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列.最坏情况的时间复杂度为O(n^2).最好情况时间复杂度为O(nlog2n).

算法描述

快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

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

    动图演示

    快速排序
    快速排序图例

    代码演示

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    /**
    *
    * 快速排序
    *
    * @param arr = {6,3,8,2,9,1}
    * @author tong.li
    *
    * 分析:
    * a. 一般以首元素或尾元素为基准,这里以首元素6为基准,有比基准数大的数放在6的右边,比基准数小的数放在6的左边,我们的目标是将6挪到序列中间的某个位置.
    * b. 假设这个位置是k,现在需要寻找这个k的位置.分别从数组的两端开始探测,先从右往左找一个小于6的数(总是如此),再从左到右找一个大于6的数,两端停下来后交换它们.
    * c. 这里可以用两个变量i和j,分布指向数组最左边和最右边.这两个变量有个好听的名字:哨兵i和哨兵j,哨兵i初始指向索引为0的6,哨兵j初始指向索引为5的1
    * 步骤:
    * 1. 先让哨兵j动起来向左(j--)找小于6的值,第一次找到为1停下来.
    * 2. 紧接着哨兵i向右移动(i++)找大于6的值,第一次找到为8停下来.
    * 3. 进行交换停下来的值,即1和8进行交换.交换后的数组为:6,3,1,2,9,8
    * 4. 在3交换后的基础上继续1,2步骤,哨兵j一直往左移遇到2,哨兵i一直往右移遇到9,两个哨兵在2已经相遇了,我们应该将基准6与和2进行交换,即交换后的数组为:2,3,1,6,9,8,此时第一轮探测真正结束
    * 此时旧基准数6已经归位,新基准数为2,以6位分界点把数组拆成了两个小数组,左数组为小于6的,右边数组都是大于6的,目前两个数组的顺序都是混乱的,不过不要紧,继续按1,2,3步骤分别对两个数组耐心处理
    * 5. 先处理6左边的小数组2,3,1,以2为基准数,找到1和3,交换后2,1,3,继续找在1相遇,交换后为1,2,3
    * 6. 再来处理6右边的小数组9,8,以9为基准数,两者在8相遇,交换后为8,9
    * 7. 到此完全结束,排序后为1,2,3,6,8,9.快速排序的每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止,排序就结束了.
    *
    */
    public static void quickSort(int[] arr, int low, int high) {
    int i, j, temp, t;
    if (low > high) {
    return;
    }
    i = low;
    j = high;
    // temp就是基准位
    temp = arr[low];

    while (i < j) {
    // 先看右边.依次往左递减
    while (temp <= arr[j] && i < j) {
    j--;
    }
    // 再看左边.依次往右递增
    while (temp >= arr[i] && i < j) {
    i++;
    }
    // 如果满足条件则交换
    if (i < j) {
    t = arr[j];
    arr[j] = arr[i];
    arr[i] = t;
    }

    }
    // 最后将基准为与i和j相等位置的数字交换
    arr[low] = arr[i];
    arr[i] = temp;
    // 递归调用左半数组
    quickSort(arr, low, j - 1);
    // 递归调用右半数组
    quickSort(arr, j + 1, high);
    }

选择排序

选择排序(Selection sort)是一种简单直观的排序算法.它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完.

算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:

  • 初始状态:无序区为R[1..n],有序区为空;
  • 第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
  • n-1趟结束,数组有序化了;

    动图演示

    选择排序

    代码演示

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    /**
    *
    * 选择排序
    *
    * @author tong.li
    * @param arr = {6,3,8,2,9,1}
    *
    *第0趟比较5次: 3,6,8,2,9,1 => 3,6,8,2,9,1 => 2,6,8,3,9,1 => 2,6,8,3,9,1 => 1,6,8,3,9,2
    *第1趟比较4次: 1,6,8,3,9,2 => 1,3,8,6,9,2 => 1,3,8,6,9,2 => 1,2,8,6,9,3
    *第2趟比较3次: 1,2,6,8,9,3 => 1,2,6,8,9,3 => 1,2,3,8,9,6
    *第3趟比较2次: 1,2,3,8,9,6 => 1,2,3,6,9,8
    *第4趟比较1次: 1,2,3,6,8,9
    */
    public static void selectionSort(int... arr) {
    if ( arr==null || arr.length <= 0) {
    return;
    }
    // 外循环控制趟数
    for (int i = 0; i < arr.length - 1; i++) {
    // 内循环控制次数
    for (int j = i + 1; j < arr.length; j++) {
    // 相邻两个元素进行比较
    if (arr[i] > arr[j]) {
    // 采用异或方式进行变量互换
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
    }
    }
    }
    }

其他排序算法后续更新,请读者持续关注.

参考文献:

十大经典排序算法-动图演示

堆排序,归并排序,快排-排序王者之争一

堆排序,归并排序,快排-排序王者之争二

支付宝打赏 微信打赏

请作者喝杯咖啡吧