数据结构与算法（八）——排序

一、排序

1、介绍

　　影响排序算法性能的几个要素：时间性能、辅助空间、算法的复杂性。
　　内部排序：将需要处理的所有数据都加载到内存中进行排序。包括交换式排序、选择式排序、插入式排序。
　　外部排序：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。包括合并排序、直接合并排序。

2、分类

　　交换式排序：冒泡排序（Bubble sort）、快速排序（Quick sort）
　　选择式排序：选择排序（Select sort）、堆排序（Heap sort）
　　插入式排序：插入排序（Insert sort）、希尔排序（Shell sort）、二叉树排序（Binary-tree sort）
　　归并式排序：归并排序（）

二、冒泡排序

1、思想

　　两个数比较大小，较大的数下沉，较小的数冒起来。每一趟至少有一个数排好，所以 n 个数至多需要 n - 1 趟。

2、过程

　　动图：

3、代码

// 冒泡排序
public static void bubbleSort(int[] arr) {
    // 冒泡排序一趟至少可以确定一个数的位置
    boolean flag = false;
    for (int i = 0; i < arr.length - 1; i++) {
        flag = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                flag = true;
            }
        }
        // 没有执行交换，已经有序
        if (!flag) {
            break;
        }
    }
}

三、快速排序

1、思想

　　快速排序：是对冒泡排序的一种改进。
　　（1）在数据集之中，选择一个元素作为"基准"（pivot）。
　　（2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
　　（3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。整个排序过程可以递归进行，以此达到整个数据有序。

2、过程

3、代码

// 快速排序
public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int l = left;
    int r = right;
    int pivot = arr[r];

    while (l < r) {
        while (l < r && arr[l] < pivot) {
            l++;
        }
        if (l < r) {
            arr[r] = arr[l];
            r--;
        }

        while (l < r && arr[r] > pivot) {
            r--;
        }
        if (l < r) {
            arr[l] = arr[r];
            l++;
        }
    }
    // 此时 l == r
    arr[l] = pivot;
    quickSort(arr, left, r - 1);
    quickSort(arr, l + 1, right);
}

四、选择排序

1、思想

　　在长度为 n 的无序数组中，
　　第一次遍历 n 个数，找到最小的数值与第一个元素交换；
　　第二次遍历n - 1个数，找到最小的数值与第二个元素交换；
　　。。。
　　第n - 1次遍历2个数，找到最小的数值与第n - 1个元素交换，排序完成。

2、过程

　　动图：

3、代码

// 选择排序.方式一、少交换
public static void selectSort(int[] arr) {
    int min = 0, index = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        min = arr[i];
        index = i;
        // 找最小值
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < min) {
                min = arr[j];
                index = j;
            }
        }
        // 将最小值与第 i 位交换
        swap(arr, i, index);
    }
}

// 选择排序.方式二、多交换
public static void selectSort2(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
                swap(arr, i, j);
            }
        }
    }
}

五、插入排序

1、思想

　　将一个数插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。

2、过程

 

　　动图：

3、代码

// 插入排序
public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        // 待插入数
        int insertVal = arr[i];
        int index = i - 1;
        while (index >= 0 && insertVal < arr[index]) {
            arr[index + 1] = arr[index];
            index--;
        }
        arr[index + 1] = insertVal;
    }
}

六、希尔排序

　　插入排序可能存在的问题，数组 arr = {2,3,4,5,6,1} 这时需要插入数 1，这样的过程是：

　　{2,3,4,5,6,6}
　　{2,3,4,5,5,6}
　　{2,3,4,4,5,6}
　　{2,3,3,4,5,6}
　　{2,2,3,4,5,6}
　　{1,2,3,4,5,6}

　　结论：当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响。

1、思想

　　希尔排序：是对插入排序的一种改进。也称为缩小增量排序。
　　在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。然后逐渐将增量减小，并重复上述过程，直至增量为1，此时数据序列基本有序，最后进行插入排序。

2、过程

　　动图：

3、代码

// 希尔排序.方式一、移位法
public static void shellSort(int[] arr) {
    // 增量 gap,并逐步缩小增量
    for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
        // 从第gap个元素,逐个对其所在的组进行直接插入排序
        for (int i = gap; i < arr.length; i++) {
            // 待插入数
            int insertVal = arr[i];
            int index = i - gap;
            while (index >= 0 && insertVal < arr[index]) {
                arr[index + gap] = arr[index];
                index = index - gap;
            }
            arr[index + gap] = insertVal;
        }
    }
}

// 希尔排序.方式二、交换法
public static void shellSort2(int[] arr) {
    // 分组.个人感觉这种方式组内排序更像是冒泡
    for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
        for (int i = gap; i < arr.length; i++) {

            for (int j = i - gap; j >= 0; j = j - gap) {
                if (arr[j] > arr[j + gap]) {
                    swap(arr, j, j + gap);
                }
            }
        }
    }
}

七、归并排序

1、思想

　　该算法采用经典的分治（divide-and-conquer）策略。分治法将问题分（divide）成一些小的问题然后递归求解，而治（conquer）的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之。

2、过程

　　分阶段：可以理解为就是递归拆分子序列的过程。

　　治阶段：将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]。

　　动图：

3、代码

// 归并排序.分+合方法
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
    if (left < right) {
        int mid = (left + right) / 2;
        // 向左递归进行分解
        mergeSort(arr, left, mid, temp);
        // 向右递归进行分解
        mergeSort(arr, mid + 1, right, temp);
        // 合并
        merge(arr, left, mid, right, temp);
    }
}

// 合并的方法
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
    int i = left;
    int j = mid + 1;
    int tempIndex = 0;

    // 1.合并两个有序序列到temp
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[tempIndex] = arr[i];
            i++;
        } else {
            temp[tempIndex] = arr[j];
            j++;
        }
        tempIndex++;

    }

    while (i <= mid) {
        temp[tempIndex] = arr[i];
        i++;
        tempIndex++;
    }
    while (j <= right) {
        temp[tempIndex] = arr[j];
        j++;
        tempIndex++;
    }

    // 2.将temp数组的元素拷贝到arr
    tempIndex = 0;
    int tempLeft = left;

    while (tempLeft <= right) {
        arr[tempLeft] = temp[tempIndex];
        tempLeft++;
        tempIndex++;
    }
}

八、基数排序

1、思想

　　基数排序（radix sort）属于"分配式排序"（distribution sort），又称"桶子法"（bucket sort）。顾名思义，将关键字按位数切割成不同的数字，然后按每个位数分别比较，这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

2、过程

　　将数组{53,3,542,748,14,214}使用基数排序，进行升序排序。

　　动图：

　　说明：
　　基数排序是对传统桶排序的扩展，速度很快。
　　基数排序是经典的空间换时间的方式，占用内存很大。当对海量数据排序时，容易造成 OutOfMemoryError。
　　有负数的数组，我们不用基数排序来进行排序。如果要支持负数，参考：https://code.i-harness.com/zh-CN/q/e98fa9

3、代码

// 基数排序
public static void radixSort(int[] arr) {
    // 定义桶的个数.0~9 一共10个
    final int bucketCount = 10;

    // 由于每一个桶都是一个一维数组,所以不难想到定义一个二维数组来表示
    int[][] buckets = new int[bucketCount][arr.length];

    // 为每一个桶定义一个指针,表示当前桶中实际放入的元素个数
    int[] indexs = new int[bucketCount];

    final int maxValueLength = getMaxValueLength(arr);
    for (int i = 0; i < maxValueLength; i++) {

        // 1.arr -> 放入桶
        for (int j : arr) {
            // 依次取个位、十位、百位……上的数字.比如取十位: 748/10=74,74%10=4
            int digit = j / (int) Math.pow(10, i) % 10;

            // 放入到对应的桶中
            buckets[digit][indexs[digit]] = j;
            // 对应桶的个数 +1
            indexs[digit]++;
        }

        // 2.从桶取 -> arr
        int temp = 0;
        // 遍历这 10 个桶
        for (int j = 0; j < bucketCount; j++) {
            if (indexs[j] > 0) {
                for (int k = 0; k < indexs[j]; k++) {
                    arr[temp] = buckets[j][k];
                    temp++;
                }
            }

            // 取完 j 号桶后,将指针归零
            indexs[j] = 0;
        }
    }
}

// 获取最大数是几位数
private static int getMaxValueLength(int[] arr) {
    int max = arr[0];
    for (int i : arr) {
        if (i > max) {
            max = i;
        }
    }

    return String.valueOf(max).length();
}

九、常用排序算法对比

　　相关术语解释：
　　1)稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
　　2)不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
　　3)内排序：所有排序操作都在内存中完成；
　　4)外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
　　5)时间复杂度： 一个算法执行所耗费的时间。
　　6)空间复杂度：运行完一个程序所需内存的大小。
　　7)n：数据规模
　　8)k："桶"的个数
　　9)In-place：不占用额外内存
　　10)Out-place：占用额外内存