数据结构与算法：排序算法

排序算法

排序算法，即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。这种新序列遵循着一定的规则，体现出一定的规律，因此，经处理后的数据便于筛选和计算，大大提高了计算效率。

排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。

排序就是把集合中的元素按照一定的次序排序在一起。一般来说有升序排列和降序排列2种排序，在算法中有8中基本排序：

1. 冒泡排序；2. 选择排序；3. 插入排序；4. 希尔排序；

2. 归并排序；6. 快速排序；7. 基数排序；8. 堆排序(涉及到二叉树)

稳定 ：在数组中有a=b，且a在b的前面，当排序后a仍然在b的前面

不稳定 ：在数组中有a=b，且a在b的前面，当排序后a可能跑到b的后面

内排序 ：所有排序操作都在内存中完成

外排序 ：因数据量过大，将数据存放在磁盘中，排序操作需通过磁盘和内存的数据传输

1. 冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

代码实现

//冒泡排序
public static void bubbleSort(int[] array){
    int temp = 0;//临时变量，用于交换
    
    //循环冒泡排序，排序次数为array.length-1次
    for (int i=0; i<array.length-1; i++){
        //遍历数组，因为要与后一个位置的数据比较，所以i要小于array.length-1，否则会报下标超出范围异常
        //又因为每进行一次排序，就会确定一个位置，所以比较次数为array.length-1-i
        for (int j=0; j<array.length-1-i; j++){
            if (array[j] > array[j+1]){//相邻俩个位置判断大小
                //如果array[j] > array[j+1]，则进行交换
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}

2. 选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是 不稳定 的排序方法。

代码实现

//选择排序
public static void selectSort(int[] array){
    int minIndex = 0;//最小值在数组中的下标
    int min = 0; //最小值

    //因为当到数组最后一个数时，只能和本身比较大小，无意义，所以i<array.length-1
    for (int i=0; i<array.length-1; i++){
        //假定array[i]在数组中为最小值
        min = array[i];
        minIndex = i;
        //从i开始，比较每个数
        for (int j=i; j<array.length; j++){
            if (min > array[j]){ //依次与当前假定的最小值进行比较
                //当数组中下标为j的值小于当前假定最小值时
                min = array[j];// 把最小值min设为array[j]
                minIndex = j; //并把下标j赋给最小值的下标minIndex，使后面能把array[i]和array[j]进行互换
            }
        }

        //退出循环后，将最小值的位置和假定最小值的位置的值进行互换
        if (minIndex != i){//如果最小值下标等于开始数的下标，即本身就是最小值，和本身互换无意义
            array[minIndex] = array[i];
            array[i] = min;
        }
    }
}

3. 插入排序

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动

代码实现

//插入排序
public static void insertSort(int[] array){
    int insertValue = 0; //插入的值
    int insertIndex = 0; //插入位置的下标,

    for (int i=1; i<array.length; i++){ //因为要和前一位比较，所以从下标1开始
        insertValue = array[i];
        insertIndex = i-1;

        //当插入位置的下标不超过数组范围且插入位置的值大于插入值时，就把插入位置的值往后移一位
        while (insertIndex >=0 && array[insertIndex] > insertValue){
            array[insertIndex+1] = array[insertIndex];//将插入位置的值往后移一位
            insertIndex--;//将插入位置的下标往前移一位，实现遍历
        }

        //当跳出while时，即插入下标位置的值小于(等于)插入值或插入位置的下标已经到-1
        //就把插入值insertValue 插入到 插入下标的后一位insertIndex+1
        array[insertIndex+1] = insertValue;
    }
}

4. 希尔排序

希尔排序(Shell's Sort)是插入排序)的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是 非稳定排序算法 。该方法因 D.L.Shell 于 1959 年提出而得名。

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

代码实现

//希尔排序（交换式）
public static void shellSort(int[] array){
    int temp = 0;//存放用于交换的临时变量
    int count = 0;//用于计算一共进行了几轮排序

    //每次间隔增量gap按照/2的规律递减，当gap<1时，就退出循环
    for (int gap = array.length/2; gap > 0; gap /=2){
        //按照gap间隔依次将数组分组后比较，如array[gap]和array[0]一组
        for (int i = gap; i<array.length; i++){
            for (int j = i-gap; j>=0; j -= gap){
                //判断组内下标小的值array[j]是否大于下标大的值array[j+gap]，如果大于则进行值交换
                if (array[j] > array[j+gap]){
                    temp = array[j];
                    array[j] = array[j+gap];
                    array[j+gap] = temp;
                }
            }
        }
    }
}

当我们将要进行排序的数组数据大小设置到10000会发现，希尔排序(交换式)并没有比插入排序快，反而慢了很多，这是因为在希尔排序中我们执行了太多次交换代码了，所以我们应该把希尔排序代码中交换的部分进行修改，改成插入排序的算法，减少数据交换的次数

//希尔排序（插入式）
public static void shellSort2(int[] array){
    for (int gap=array.length/2; gap>0; gap /=2){
        for (int i=gap; i<array.length; i++){
            //修改成插入排序的算法
            int j = i;
            int temp = array[j];
            //因为我们按照了间隔增量分组，所以比较时要和组内的值比较
            while (j - gap >=0 && temp < array[j-gap]){
                array[j] = array[j-gap];zeng
                j -= gap;//同理，遍历时也要按照间隔增量递减
            }
            array[j] = temp;
        }
    }
}

5. 快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

代码实现

//快速排序
public static void quickSort(int[] array, int left, int right){
    //创建俩个指针
    int l = left;//指向中心值左边遍历开始位置的下标
    int r = right;//指向中心值右边遍历开始位置的下标

    //中心值(中心值的位置并不一定指向数组中心，它会随着遍历而发生位置交换)
    int pivot = array[(left+right)/2];

    int temp = 0;//临时变量，用于交换时使用

    //俩个指针依次往中心值移动，直到中心值所在位置的左边都小于中心值和右边都大于中心值
    while (l < r){
        //如果左指针所指数值小于中心值，则指针往右移一位，直到所指数值大于中心值
        while (array[l] < pivot){
            l++;
        }

        //如果右指针所指数值大于中心值，则指针往左移一位，直到所指数值小于中心值
        while(array[r] > pivot){
            r--;
        }

        //如果指针移动时经过另一个指针或俩个指针指向同一个位置时，
        //说明中心值的左边都小于中心值，右边都大于中心值，则退出循环
        if (l >= r){
            break;
        }

        //将俩个指针指向位置的数值进行交换
        temp = array[l];
        array[l] = array[r];
        array[r] = temp;

        //如果交换后，有个指针指向的数值等于中心值，即中心值的位置发生了变换
        //又因为，另一个指针所指的数值是交换后符合条件的，
        //所以另一个指针应该继续移动一位，往中心值靠
        if (array[l] == pivot){
            r--;
        }
        if (array[r] == pivot){
            l++;
        }
    }

    //循环退出后，俩个指针会指向同一个位置，这时中心值俩边都符合条件
    //就要把俩个指针的位置继续移一位，使得后面可以通过递归重新赋予中心值
    if (l == r){
        l++;
        r--;
    }

    //当原先左指针指向的下标left还小于循环后的右指针下标r时，
    //说明left到r之间可能还有需要排序的的数值，继续递归
    if (left < r){
        quickSort(array, left, r);
    }
    //当原先右指针指向的下标right还大于循环后的左指针下标l时，
    //说明right到l之间可能还有需要排序的的数值，继续递归
    if (right > l){
        quickSort(array, l, right);
    }
}

6. 归并排序

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

代码实现

/**
 * 归并 - 分
 * @param array 排序数组
 * @param left 数组左标，开始为0
 * @param right 数组的右标，开始为数组的最大下标array.length-1
 * @param temp 辅助数组，用于数组的分和合
 */
public static void mergerSort(int[] array, int left, int right, int[] temp){
    //判断是否已经分到尽头，即左标和右标重合
    if (left < right){
        //选出中心点
        int mid = (left + right) / 2;
        //从中心点开始向左递归，进行分离
        mergerSort(array, left, mid, temp);
        //从中心点开始向右递归，进行分离
        mergerSort(array, mid+1, right, temp);
        //当向右或向左递归到尽头时，这时开始递归返回，进行合并
        merger(array, left, mid, right, temp);
    }
}

/**
 * 归并 - 合
 * @param array 排序数组
 * @param left 数组左标
 * @param mid 数组中心点
 * @param right 数组右标
 * @param temp 辅助数组
 */
public static void merger(int[] array, int left, int mid, int right, int[] temp){
    int i = left;//储存左段的左标
    int j = mid+1;//储存右端的左标
    int t = 0;//辅助数组的下标

    //从各段左标开始，依次进行大小比较，比较后再把小的一方放入辅助数组，再把该段的左标和辅助数组下标往右移一位
    while (i<=mid && j<=right){//当左段或右段已经迭代到尽头时，则退出循环
        if (array[i] < array[j]){// 左段左标小于右段左标
            temp[t] = array[i];
            i++;
            t++;
        }else { //右段左标小于左段左标
            temp[t] = array[j];
            j++;
            t++;
        }
    }

    //当比较循环退出后，即有一段的数据已经全部放进辅助数组中
    //又因为段内的数据有序的，所以只需将剩下的数据依次放进辅助数组即可
    while (i <= mid){//左段的数据还没有全部放进辅助数组
        temp[t] = array[i];
        i++;
        t++;
    }
    while (j <= right){//右段的数据还没有全部放进辅助数组
        temp[t] = array[j];
        j++;
        t++;
    }

    //将辅助数组内的所有数据复制到原始数组中
    t = 0;
    int tempLeft = left;//原始数组赋值下标，开始值是传入的left参数
    //当赋值下标tempLeft > 数组右标时，即此次合并的数据已经全部复制到原始数组，就退出循环
    while (tempLeft <= right){
        //当此次合并的数据还有未复制到原始数组的数据时，则进行复制
        //复制后要将原始数组赋值下标和辅助数组下标往右移一位
        array[tempLeft] = temp[t];
        tempLeft++;
        t++;
    }
}

7. 基数排序

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于 稳定性 的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

注意：基数排序的效率虽然高于其他稳定排序法，但是基数排序的内存损耗较大，是典型的 空间换时间 的算法

代码实现

//基数排序
public static void radixSort(int[] array){
    //获取数组中数据的最大位数，即最大数的位数
    int max = array[0];
    //循环遍历找出数组中的最大数
    for (int i=1; i<array.length; i++){
        if (max < array[i]){
            max = array[i];
        }
    }
    //数组中最大数的字符串长度就是数组中数据的最大位数
    int maxLength = (max+"").length();

    //基数桶，一共右10个，对应0到9
    //为了防止可能的溢出，桶的大小要设置为最大，即要进行排序的数组大小
    int[][] buckets = new int[10][array.length];

    //每个桶存放的有效数据个数，用于后面从桶中取回数据
    int[] bucketEleCount = new int[10];

    //遍历循环数组内数据的每个位数上的元素，并放入对应的基数桶
    for (int i=0, n=1; i<maxLength; i++, n *=10){//循环的次数为最大位数
        for (int j=0; j<array.length; j++){
            int digitOfElement = array[j] /n %10;//获取对应位数上的元素
            /*
            buckets[对应基数桶][数据在桶中存放的位置]
            对应基数桶：该数据array[j]在对应位数上的元素，即digitOfElement
            数据在桶中存放的位置：就是该基数桶中的有效数据个数(因为数组是从0开始，因而不用+1)
             */
            buckets[digitOfElement][bucketEleCount[digitOfElement]] = array[j];
            bucketEleCount[digitOfElement]++;//放入基数桶后，要把该基数桶的有效数据个数+1
        }

        //当把原始数组中的数据都放入桶中后，再按照0到9的顺序依次从桶中取出数据放回原始数组
        int index = 0;//原始数组存入下标
        for (int j=0; j<bucketEleCount.length; j++){//按照顺序遍历各个基数桶
            if (bucketEleCount[j] != 0){//判断该基数桶是否有有效数据
                for (int e=0; e<bucketEleCount[j]; e++){//遍历桶中的有效数据
                    //将桶中的有效数据放回原始数组
                    array[index] = buckets[j][e];
                    index++;
                }
            }
            //因桶中的有效数据已被取回到原始数组，所有该桶的有效数据个数需清零
            bucketEleCount[j] = 0;
        }
    }
}