数据结构和算法8-排序-白红宇

数据结构和算法8-排序

阅读量：4302 次

发布时间：2019-05-27

本文共 5427 字，大约阅读时间需要 18 分钟。

数据结构和算法系列共八篇

到这，数据结构和算法八篇都学完。这只算是算法的入门而已，后面还需继续努力。

1.排序概念

假设含有n个记录的序列为{r1,r2,…,rn}，其相应的关键字分别为{k1,k2,…,…kn}，需确定1，2，….，n的一种排列p1,p2,…,pn,

使其相应的关键字满kp1≤kp2≤…≤kpn(非递减或非递增)关系，即使得序列成为一个按关键字有序的序列{rp1,rp2,…,rpn}，这样的操作为排序。

1-1.内部排序和外部排序

都在内存器中进行是内部排序，

内存中无法完成全部排序要借助外部存储才能完成时外部排序。

1-2.稳定排序和不稳定排序

每次排序的结果可能不一样。

比如当成绩相同，再按照学号小的在前，这样就是稳定的。
如果不加上这个学号小的在前，如果每次排序不同，就是不稳定排序。

1-3.比较排序和非比较排序

大部分的排序都是基于比较的，但也有例外(比如：计数排序、基数排序不需要进行比较)

比较排序又分为：插入排序、交换排序、选择排序、归并排序

1-4.影响因素

时间性能：排序算法的时间开销是衡量其好坏的最重要的标识。在内排序中，主要进行两种操作就是比较和移动，所以高效率的内排序算法应该尽可能少的比较和移动次数。

辅助空间：存放待排序所占用的存储空间之外和执行算法所需要的其他存储空间

算法的复杂性：算法本身的复杂性。

2.插入排序

2-1.直接插入排序

直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数加一的有序表。

public class SortInsertDirect {
       public static void main(String[] args) {
           int[] data = {
   1, 4, 3, 6, 5, 2, 7};        System.out.println(Arrays.toString(data));        sortByInsertDirect(data);        System.out.println(Arrays.toString(data));    }    private static void sortByInsertDirect(int[] data) {
           for (int i = 0; i < data.length - 1; i++) {
               int next = data[i + 1];            // 比如：1，3, 4, 6 时，要5操作对前面操作            // i = 4            if (next < data[i]) {
                   for (int j = i; j > -1; j--) {
                       // next比前面排好序的小时，将排序好的元素移动往后移一位                    if (next < data[j]) {
                           data[j + 1] = data[j];                    } else {
                           // 将值放到j+1位置，并进入下一次循环，因为前面都是有序                        data[j + 1] = next;                        break;                    }                }            }        }    }}

2-2.希尔排序

希尔排序算是对简单插入排序的一种改进，属于一种增量式的排序算法。

希尔排序是把序列按一定间隔分组，对每组使用直接插入排序；随着间隔减小，一直到1，使得整个序列有序

3.选择排序

3-1.选择排序

第一次无序数列中选出最小的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小元素，然后放到有序序列的末尾。

public class SortSelectDirect {
       public static void main(String[] args) {
           int[] data = {
   1, 4, 3, 6, 5, 2, 7};        System.out.println(Arrays.toString(data));        sortBySelectDirect(data);        System.out.println(Arrays.toString(data));    }    private static void sortBySelectDirect(int[] data) {
           for (int i = 0; i < data.length; i++) {
               int min = i;            // 找出最小的index            for (int j = i; j < data.length; j++) {
                   if (data[j] < data[min]) {
                       min = j;                }            }            // 交换i和最小index坐标值            int tmp = data[i];            data[i] = data[min];            data[min] = tmp;        }    }}

3-2.堆排序

步骤：

1.将长度为n的待排序的数组进行堆有序化构造成一个大顶堆
2.将根节点与尾节点交换并输出此时的尾节点
3.将剩余的n -1个节点重新进行堆有序化
4.重复步骤2，步骤3直至构造成一个有序序列

4.交换排序

4-1.冒泡排序

两两比较相邻记录的关键字，如果反序则交换，知道没有反序的记录为止

public class SortBubble {
       public static void main(String[] args) {
           int[] data = {
   1, 4, 3, 6, 5, 2, 7};        System.out.println(Arrays.toString(data));        sortByBubble(data);        System.out.println(Arrays.toString(data));    }    private static void sortByBubble(int[] data) {
           // 保证交换出的一段是有序的，不管是头还是尾，有序端，不用在外层再遍历        // 由前向后        for (int i = 0; i < data.length; i++) {
               for (int j = 0; j < data.length - i - 1; j++) {
                   // 保证前面的有序，由小到大                if (data[j] > data[j + 1]) {
                       int tmp = data[j];                    data[j] = data[j + 1];                    data[j + 1] = tmp;                }            }        }        // 由后向前        // for (int i = data.length - 1; i > 0; i--) {
           //     // 保证后面有序，由小到大        //     for (int j = 0; j < i - 1; j++) {
           //         if (data[j] > data[j + 1]) {
           //             int tmp = data[j];        //             data[j] = data[j + 1];        //             data[j + 1] = tmp;        //         }        //     }        // }    }}

4-2.快速排序

思想：使用分而治之和递归的方式

先从数组中选出一个基数 (简单起见可以选第一个)

分区过程，将比基数大的放右边，比基数小的放左边

递归，在堆左和右区间，进行上面两个步骤，直到各个区间为一个数

步骤

public class SortQuick {
       public static void main(String[] args) {
           int[] data = {
   1, 4, 3, 6, 5, 2, 7};        System.out.println(Arrays.toString(data));        quickSort(data);        System.out.println(Arrays.toString(data));    }    public static void quickSort(int[] arr) {
           int low = 0;        int high = arr.length - 1;        quickSort(arr, low, high);    }    public static void quickSort(int[] arr, int low, int high) {
           if (low < high) {
               // 分区            int mid = partition(arr, low, high);            // 左侧递归            quickSort(arr, low, mid - 1);            // 右测递归            quickSort(arr, mid + 1, high);        }    }    public static int partition(int[] arr, int low, int high) {
           int i = low;        int j = high;        // 基准数        int temp = arr[low];        while (i < j) {
               // 一直找到右侧小于基准数的，并且得保证i
   
     temp && i < j) {
                   j--;            }            // 将左侧的空位填上，右测找到小于基准的数，并i++            if (i < j) {
                   arr[i] = arr[j];                i++;            }            // 一直找到左侧大于基准数的，并且得保证i