黑马程序员技术交流社区

标题: 大自然的搬运工 [打印本页]

---

作者: 蓝猫淘气    时间: 2020-1-10 15:43
标题: 大自然的搬运工
概述
排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。我们这里说说八大排序就是内部排序。


插入排序
思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的子序列的合适位置，直到全部插入排序完为止。
关键问题：在前面已经排好序的序列中找到合适的插入位置。
方法：

直接插入排序
二分插入排序
希尔排序
直接插入排序
① 基本思想

每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的子序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。



② 算法实现

首先需要定义一个待排序的数组：

int a[] = {3,1,5,7,2,4,9,6,10,8};
1
    /**
     * 直接插入排序
     * @param v
     */
    public void insertSort(View v) {
        for (int i = 1; i < a.length; i++) {
            // 待插入元素
            int temp = a[i];
            int j;
            for (j = i - 1; j >= 0 && a[j] > temp; j--) {
                // 将大于temp的往后移动一位
                a[j + 1] = a[j];
            }
            a[j + 1] = temp;
        }
    }

③ 复杂度

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

时间复杂度：O（n^2）
空间复杂度：O（1）
二分插入排序
① 基本思想

二分法插入排序的思想和直接插入一样，只是找合适的插入位置的方式不同，这里是按二分法找到合适的位置，可以减少比较的次数。



② 算法实现

    /**
     * 二分插入排序
     * @param v
     */
    public void twoInsertSort(View v) {
        for (int i = 0; i < a.length; i++) {
            int temp = a[i];
            int left = 0;
            int right = i - 1;
            int mid;
            while (left <= right) {
                mid = (left + right) / 2;
                if (temp < a[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            for (int j = i - 1; j >= left; j--) {
                a[j + 1] = a[j];
            }
            if (left != i) {
                a[left] = temp;
            }
        }
    }

希尔排序
① 基本思想

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2《d1重复上述的分组和排序，直至所取的增量dt=1(dt《dt-1《…《d2《d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。



② 算法实现

    /**
     * 希尔排序
     * @param v
     */
    public void shellSort(View v) {
        int dk = a.length/2;
        while(dk >= 1){
            ShellInsertSort(a, dk);
            dk = dk/2;
        }
        after.setText(getText(a));
    }
    private void ShellInsertSort(int[] a, int dk) {//类似插入排序，只是插入排序增量是1，这里增量是dk,把1换成dk就可以了
        for (int i = dk; i < a.length; i++) {
            // 待插入元素
            int temp = a[i];
            int j;
            for (j = i - dk; j >= 0 && a[j] > temp; j = j-dk) {
                // 将大于temp的往后移动dk位
                a[j + dk] = a[j];
            }
            a[j + dk] = temp;
        }
    }

③ 复杂度

希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列d的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：增量因子中除1 外没有公因子，且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。

时间复杂度：O（nlog2n）
空间复杂度：O（1）
选择排序
思想：每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完。
关键问题：在剩余的待排序记录序列中找到最小关键码记录。
方法：

简单选择排序
二元选择排序
堆排序
简单选择排序
① 基本思想

在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。



② 算法实现

    /**
     * 简单选择排序
     * @param v
     */
    public void selectSort(View v) {
        int min;
        for(int i = 0; i < a.length; i++){
            min = i;
            for(int j = i + 1; j < a.length; j++){//找到最小值下标
                if(a[j] < a[min]){
                   min = j;
                }
            }
            swap(a, i, min);
        }
    }

③ 复杂度

时间复杂度：O（n2）
空间复杂度：O（1）
二元选择排序
① 基本思想

简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。

② 算法实现

    /**
     * 二元选择排序
     * @param v
     */
    public void twoSelectSort(View v) {
        int min, max;
        for(int i = 0; i < a.length/2; i++){
            min = i; max = i; //分别记录最大和最小关键字记录位置
            for(int j = i + 1; j< a.length - i; j++){
                if (a[j] > a[max]) {
                    max = j;
                    continue;
                 }
                if (a[j] < a[min]) {
                    min = j;
                }
            }
            swap(a, i, min); //最小值放到前面
            if (i == max) {
                max = min; //如果当前i就是max，第一次排序后max要调整为min（a[i]新的位置是a[min]）
            }
            swap(a, a.length-1-i, max); //最大值放到后面
        }
    }

堆排序
① 基本思想

堆排序是一种树形选择排序，是对直接选择排序的有效改进。
堆的定义下：具有n个元素的序列（k1,k2,…,kn),当且仅当满足下面条件时称之为堆。

在这里只讨论满足后者条件的堆（大顶堆）。若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有结点的值均大于等于其子女结点的值，根结点（堆顶元素）的值是最大的。

思想：初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

初始序列：46,79,56,38,40,84
建堆：

交换，从堆中踢出最大数

依次类推：最后堆中剩余的最后两个结点交换，踢出一个，排序完成。

因此，实现堆排序需解决两个问题：

如何将n 个待排序的数建成堆；
输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。
首先讨论第二个问题：输出堆顶元素后，对剩余n-1元素重新建成堆的调整过程。
调整大顶堆的方法：
1）设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。
2）将根结点与左、右子树中较大元素的进行交换。
3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法 （2）.
4）若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法 （2）.
5）继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。
称这个自根结点到叶子结点的调整过程为筛选。

再讨论对n 个元素初始建堆的过程。
建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。
1）n 个结点的完全二叉树，则最后一个结点是第n/2个结点的子树。
2）筛选从第n/2个结点为根的子树开始，该子树成为堆。
3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

② 算法实现

/**
     * 堆排序
     * @param v
     */
public void heapSort(View v) {
     for (int i = 0; i < a.length; i++) {
         createMaxHeap(a, a.length - 1 - i);
         swap(a, 0, a.length - 1 - i);
     }
}

public void createMaxHeap(int[] data, int lastIndex) {
        // 从lastIndex处节点（最后一个节点）的父节点开始
        for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
            // 保存当前正在判断的节点
            int k = i;
            // 如果当前k节点的子节点存在
            while (2 * k + 1 <= lastIndex) {
                // biggerIndex总是记录较大节点的值,先赋值为当前节点的左子节点的索引
                int biggerIndex = 2 * k + 1;
                // 若当前节点的右子节点存在
                if (biggerIndex + 1 <= lastIndex) {
                    if (data[biggerIndex] < data[biggerIndex + 1]) {
                        // 若右子节点值比左子节点值大，则biggerIndex记录的是右子节点的索引
                        biggerIndex++;
                    }
                }
                // 如果k节点的值小于其较大的子节点的值
                if (data[k] < data[biggerIndex]) {
                    // 交换两者的值
                    swap(data, k, biggerIndex);
                    // 将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
                    k = biggerIndex;
                } else {
                    break;
                }
            }
        }
    }

③ 复杂度

设树深度为k，。从根到叶的筛选，元素比较次数至多2(k-1)次，交换记录至多k 次。所以，在建好堆后，排序过程中的筛选次数不超过下式：



而建堆时的比较次数不超过4n 次，因此堆排序最坏情况下，时间复杂度也为：O(nlogn )。

时间复杂度：O(nlogn )
空间复杂度：O（1）
交换排序
方法：

冒泡排序
快速排序
冒泡排序
① 基本思想

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。



② 算法实现

    /**
     * 冒泡排序
     * @param v
     */
    public void bubbleSort(View v) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length - i - 1; j++) {
                // 每遍历一次都把最大的数沉到最底下去了
                if (a[j] > a[j + 1]) {
                    swap(a, j, j + 1);
                }
            }
        }
    }

③ 复杂度

时间复杂度：O（n2）
空间复杂度：O（1）
改进的冒泡排序
① 基本思想

传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

② 算法实现

    /**
     * 冒泡排序改进
     * @param v
     */
    public void bubbleSort2(View v) {
        int low = 0;
        int high= a.length -1; //设置变量的初始值
        int i;
        while (low < high) {
            for (i = low; i < high; i++) //正向冒泡,找到最大者
                if (a[i]> a[i + 1]) {
                    swap(a, i, i + 1);
                }
            --high;//修改high值, 前移一位
            for (i = high; i > low; i--) //反向冒泡,找到最小者
                if (a[i]<a[i-1]) {
                    swap(a, i, i - 1);
                }
            ++low;//修改low值,后移一位
        }
    }

快速排序
① 基本思想

选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。



② 算法实现

    /**
     * 快速排序
     * @param
     */
    public void quickSort(View v) {
        quickSort(a, 0 , a.length - 1);
        after.setText(getText(a));
    }

    private  void quickSort(int[] a,int low, int high) {
        if(low < high){ //如果不加这个判断递归会无法退出导致堆栈溢出异常
            int middle = getMiddle(a, low, high);
            quickSort(a, 0, middle-1);  //递归对低子表递归排序
            quickSort(a, middle + 1, high);  //递归对高子表递归排序
        }
    }

    public int getMiddle(int[] a, int low, int high){
        int key = a[low];//基准元素，排序中会空出来一个位置
        while(low < high){
            while(low < high && a[high] >= key){//从high开始找比基准小的，与low换位置
                high--;
            }
            a[low]=a[high];
            while(low < high && a[low] <= key){//从low开始找比基准大,放到之前high空出来的位置上
                low++;
            }
            a[high] = a[low];
        }
        a[low] = key;//此时low=high 是基准元素的位置，也是空出来的那个位置
        return low;
    }
③ 复杂度

快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快速排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

时间复杂度：O（nlog2n）
空间复杂度：O（nlog2n）
改进的快速排序
① 基本思想

在本改进算法中,只对长度大于k的子序列递归调用快速排序,让原序列基本有序，然后再对整个基本有序序列用插入排序算法排序。实践证明，改进后的算法时间复杂度有所降低，且当k取值为 8 左右时,改进算法的性能最佳。

② 算法实现

   /**
     * 快速排序改进
     * @param
     */
    public void quickSort2(View v) {
        quickSort2(a, 0, a.length - 1, 8);//先调用改进算法Qsort使之基本有序,k=8
        //再用插入排序对基本有序序列排序
        for(int i = 1; i < a.length; i++){
            int temp = a[i];
            int j;
            for (j = i - 1; j >= 0 && a[j] > temp; j--) {
                // 将大于temp的往后移动一位
                a[j + 1] = a[j];
            }
            a[j + 1] = temp;
        }
    }

    private void quickSort2(int[] a,int low, int high, int k) {
        if(high -low > k) { //长度大于k时递归, k为指定的数
            int pivot = partition(a, low, high); // 调用的Partition算法保持不变
            quickSort2(a, low, pivot - 1, k);
            quickSort2(a, pivot + 1, high, k);
        }
    }

    private int partition(int a[], int low, int high) {
        int privotKey = a[low]; //基准元素
        while(low < high){   //从表的两端交替地向中间扫描
            while(low < high  && a[high] >= privotKey) { //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端
                high--;
            }
            swap(a, low, high);
            while(low < high  && a[low] <= privotKey ) {
                low++;
            }
            swap(a, low, high);
        }
        return low;
    }
归并排序
① 基本思想

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。



② 算法实现

    /**
     * 归并排序
     * @param
     */
    public void mergeSort(View v) {
        mergeSort(a, 0 , a.length - 1);
    }

    public void mergeSort(int[] a, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            // 左边
            mergeSort(a, low, mid);
            // 右边
            mergeSort(a, mid + 1, high);
            // 左右归并
            merge(a, low, mid, high);
        }
    }

    public void merge(int[] a, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;// 左指针
        int j = mid + 1;// 右指针
        int k = 0;
        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (a[i] < a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }
        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = a[i++];
        }
        // 把右边边剩余的数移入数组
        while (j <= high) {
            temp[k++] = a[j++];
        }
        // 把新数组中的数覆盖a数组
        for (int k2 = 0; k2 < temp.length; k2++) {
            a[low + k2] = temp[k2];
        }
    }

③ 复杂度

时间复杂度：O（nlog2n）
空间复杂度：O（n）
桶排序/基数排序
① 基本思想

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。



② 算法实现

    /**
     * 桶排序/基数排序
     * @param
     */
    public void radixSort(View v) {
        // 找到最大数，确定要排序几趟
        int max = 0;
        for (int i = 0; i < a.length; i++) {
            if (max < a[i]) {
                max = a[i];
            }
        }
        // 判断位数
        int times = 0;
        while (max > 0)  {
            max = max / 10;
            times++;
        }
        // 建立十个队列
        List<ArrayList> queue = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            ArrayList queue1 = new ArrayList();
            queue.add(queue1);
        }
        // 进行times次分配和收集
        for (int i = 0; i < times; i++) {
            // 分配
            for (int j = 0; j < a.length; j++) {
                int x = a[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
                ArrayList queue2 = queue.get(x);
                queue2.add(a[j]);
                queue.set(x, queue2);
            }
            // 收集
            int count = 0;
            for (int j = 0; j < 10; j++) {
                while (queue.get(j).size() > 0) {
                    ArrayList<Integer> queue3 = queue.get(j);
                    a[count] = queue3.get(0);
                    queue3.remove(0);
                    count++;
                }
            }
        }
    }

③ 复杂度

时间复杂度：O（d（n+r））
空间复杂度：O（n+r）
复杂度总结




时间复杂度：

（1）平方阶(O(n2))排序

直接插入
直接选择
冒泡排序
（2）线性对数阶(O(nlog2n))排序

希尔排序
堆排序
快速排序
归并排序
（3）线性阶(O(n))排序

基数排序
说明：
当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；
而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；
原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

稳定性：

排序算法的稳定性：若待排序的序列中，存在多个具有相同关键字的记录，经过排序， 这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对 次序发生了改变，则称该算法是不稳定的。

稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较。

（1）稳定的排序算法

直接插入排序
冒泡排序
归并排序
基数排序
（2）不是稳定的排序算法

希尔排序
简单选择排序
堆排序
快速排序
排序算法选择：

1）当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。

快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
归并排序：它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。
2） 当n较大，内存空间允许，且要求稳定性 =》归并排序
3） 当n较小，可采用直接插入或直接选择排序。

直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。
直接选择排序 ：元素分布有序，如果不要求稳定性，选择直接选择排序
5）一般不使用或不直接使用传统的冒泡排序。
6）基数排序
它是一种稳定的排序算法，但有一定的局限性：

关键字可分解
记录的关键字位数较少，如果密集更好
如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2