精华内容
下载资源
问答
  • 归并排序与希尔排序介绍 归并排序 归并排序的思想很简单,如果有一组待排序列,先切分再重组。任何一篇教程也都会说采用的是分治法,意思就是这么个意思,再细致一点的理解就是: 将一组待排序,先分割成一个一个的...

    归并排序与希尔排序介绍

    归并排序

    归并排序的思想很简单,如果有一组待排序列,先切分再重组。任何一篇教程也都会说采用的是分治法,意思就是这么个意思,再细致一点的理解就是:

    将一组待排序,先分割成一个一个的元素,然后将这些元素先两两排序,再四四排序,八八排序,一直到排序完所有的元素。

    也就是说归并排序其实就是将已有序的子序列合并,得到完全有序的序列。我们看一张动图来认识一下:

    1 动画展示

    在这里插入图片描述

    是不是有点理解了,动态图的作用其实就是为了方便你了解整个归并过程,不理解也没关系,我们再来看一张静态图,帮助你从细节上来理解。

    在这里插入图片描述

    上面的这张图基本上能把整个归并排序的流程了解清楚了。也就是文章开头提到的先切分再重组。下面我们使用代码来实现一下归并排序,并对其做一个改进:

    2 代码实现

    基本实现的思想很简单,我们就是先切分成一个个元素,然后再合并就好了。

    • 合并数组
    //合并方法
        private static void merge(int[] arr, int low, int mid, int high, int[] temp) {
            int i = low; // 初始化i, 左边有序序列的初始索引
            int j = mid + 1; //初始化j, 右边有序序列的初始索引
            int t = 0; // 指向temp数组的当前索引
            //先把左右两边(有序)的数据按照规则填充到temp数组
            //直到左右两边的有序序列,有一边处理完毕为止
            while(i <= mid&&j <= high){
                //如果左边的有序序列的当前元素,小于等于右边有序序列的当前元素
                //即将左边的当前元素,填充到temp数组
                //然后 t++, i++
                if(arr[i] <= arr[j]){
                    temp[t] = arr[i];
                    t++;
                    i++;
                }else{
                    //反之,将右边有序序列的当前元素,填充到temp数组
                    temp[t] = arr[j];
                    t++;
                    j++;
                }
            }
            //把有剩余数据的一边的数据依次全部填充到temp
            while( i <= mid) { //左边的有序序列还有剩余的元素,就全部填充到temp
                temp[t] = arr[i];
                t++;
                i++;
            }
            while( j <= high) { //右边的有序序列还有剩余的元素,就全部填充到temp
                temp[t] = arr[j];
                t++;
                j++;
            }
            //将temp数组的元素拷贝到arr
            //注意,并不是每次都拷贝所有,这句话和递归有关,要理解有一定的难度
            //因为这里并不是全部分完之后再合,而是分一点合一点
            t = 0;
            int tempLow = low; //
            //第一次合并 tempLow = 0 , high = 1 //  tempLow = 2  high = 3 // tL=0 ri=3
            //最后一次 tempLow = 0  high = 7
            while(tempLow <= high) {
                arr[tempLow] = temp[t];
                t += 1;
                tempLow += 1;
            }
        }
    
    • 归并排序代码
     //归并排序代码
        //主要思路,先递归拆分数组,然后再合并数组
        public static void mergeSort(int arr[],int low,int high,int temp[]){
            if(low < high){
                int mid = (low + high) / 2;
                //左递归进行拆分
                mergeSort(arr,low,mid,temp);
                //右递归进行拆分
                mergeSort(arr,mid + 1,high,temp);
                //合并
                merge(arr,low,mid,high,temp);
            }
        }
    
    • 全部代码
    package com.homyit;
    
    import java.util.Arrays;
    
    public class MergeSortDemo {
        //归并排序代码
        //主要思路,先递归拆分数组,然后再合并数组
        public static void mergeSort(int arr[],int low,int high,int temp[]){
            if(low < high){
                int mid = (low + high) / 2;
                //左递归进行拆分
                mergeSort(arr,low,mid,temp);
                //右递归进行拆分
                mergeSort(arr,mid + 1,high,temp);
                //合并
                merge(arr,low,mid,high,temp);
            }
        }
        //合并方法
        private static void merge(int[] arr, int low, int mid, int high, int[] temp) {
            int i = low; // 初始化i, 左边有序序列的初始索引
            int j = mid + 1; //初始化j, 右边有序序列的初始索引
            int t = 0; // 指向temp数组的当前索引
            //先把左右两边(有序)的数据按照规则填充到temp数组
            //直到左右两边的有序序列,有一边处理完毕为止
            while(i <= mid&&j <= high){
                //如果左边的有序序列的当前元素,小于等于右边有序序列的当前元素
                //即将左边的当前元素,填充到temp数组
                //然后 t++, i++
                if(arr[i] <= arr[j]){
                    temp[t] = arr[i];
                    t++;
                    i++;
                }else{
                    //反之,将右边有序序列的当前元素,填充到temp数组
                    temp[t] = arr[j];
                    t++;
                    j++;
                }
            }
            //把有剩余数据的一边的数据依次全部填充到temp
            while( i <= mid) { //左边的有序序列还有剩余的元素,就全部填充到temp
                temp[t] = arr[i];
                t++;
                i++;
            }
            while( j <= high) { //右边的有序序列还有剩余的元素,就全部填充到temp
                temp[t] = arr[j];
                t++;
                j++;
            }
            //将temp数组的元素拷贝到arr
            //注意,并不是每次都拷贝所有,这句话和递归有关,要理解有一定的难度
            //因为这里并不是全部分完之后再合,而是分一点合一点
            t = 0;
            int tempLow = low; //
            //第一次合并 tempLow = 0 , high = 1 //  tempLow = 2  high = 3 // tL=0 ri=3
            //最后一次 tempLow = 0  high = 7
            while(tempLow <= high) {
                arr[tempLow] = temp[t];
                t += 1;
                tempLow += 1;
            }
        }
    
        public static void main(String[] args) {
            int arr[] = {8, 4, 5, 7, 1, 3, 6, 2};
            int temp[] = new int[arr.length]; //归并排序需要一个额外空间
            System.out.println("排序前的结果为:" + Arrays.toString(arr));
            mergeSort(arr, 0, arr.length - 1, temp);
            System.out.println("排序后的结果为:" + Arrays.toString(arr));
        }
    }
    

    输出结果如下:

    排序前的结果为:[8, 4, 5, 7, 1, 3, 6, 2]
    排序后的结果为:[1, 2, 3, 4, 5, 6, 7, 8]

    希尔排序

    希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位;

    希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

    1 动画展示

    在这里插入图片描述

    2 代码实现

    • 希尔排序代码
    public static void shellSort(int arr[]){
            //遍历步长,每遍历了一轮步长除以2,直到小于等于0结束循环
            for(int step = (arr.length) / 2;step > 0;step /= 2){
                //遍历每个元素
                for(int i = step;i < arr.length;i++){
                    //遍历本步长数组中的元素
                    for(int j = i - step;j >= 0;j -= step){
                        //将当前元素与加上步长的元素对比
                        //如果当前元素大舅交换位置
                        if(arr[j] > arr[j+step]){
                            //交换位置
                            int temp = arr[j];
                            arr[j] = arr[j + step];
                            arr[j + step] = temp;
                        }
                    }
                }
            }
        }
    
    • 完整代码
    package com.homyit;
    
    import java.util.Arrays;
    
    public class ShellSortDemo {
        public static void shellSort(int arr[]){
            //遍历步长,每遍历了一轮步长除以2,直到小于等于0结束循环
            for(int step = (arr.length) / 2;step > 0;step /= 2){
                //遍历每个元素
                for(int i = step;i < arr.length;i++){
                    //遍历本步长数组中的元素
                    for(int j = i - step;j >= 0;j -= step){
                        //将当前元素与加上步长的元素对比
                        //如果当前元素大舅交换位置
                        if(arr[j] > arr[j+step]){
                            //交换位置
                            int temp = arr[j];
                            arr[j] = arr[j + step];
                            arr[j + step] = temp;
                        }
                    }
                }
            }
        }
        public static void main(String[] args) {
            int arr[] = {8, 4, 5, 7, 1, 3, 6, 2};
            System.out.println("排序前的结果为:" + Arrays.toString(arr));
            shellSort(arr);
            System.out.println("排序后的结果为:" + Arrays.toString(arr));
        }
    }
    

    两种排序比较

    方法 时间复杂度(平均) 时间复杂度(最好) 时间复杂度(最坏) 空间复杂度 稳定性
    归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定
    希尔排序 O(nlog2n)-O(n^2) O(n) O(n^2) O(1) 不稳定
    展开全文
  • 希尔排序希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。 希尔排序是把记录按下标的一定...

    希尔排序希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。希尔排序过程希尔排序的基本思想是:将数组列在一个表中并对列分别进行插入排序,重复这过程,不过每次用更长的列(步长更长了,列数更少了)来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法,算法本身还是使用数组进行排序。例如,假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果我们以步长为5开始进行排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样(竖着的元素是步长组成):13 14 94 33 82
    25 59 94 65 23
    45 27 73 25 39
    10
    然后我们对每列进行排序:10 14 73 25 23
    13 27 94 33 39
    25 59 94 65 82
    45
    将上述四行数字,依序接在一起时我们得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。这时10已经移至正确位置了,然后再以3为步长进行排序:10 14 73
    25 23 13
    27 94 33
    39 25 59
    94 65 82
    45
    排序之后变为:10 14 13
    25 23 33
    27 25 59
    39 65 73
    45 94 82
    94
    最后以1步长进行排序(此时就是简单的插入排序了)
    def shell_sort(alist):
    n = len(alist)
    # 初始步长
    gap = n / 2
    while gap > 0:
    # 按步长进行插入排序
    for i in range(gap, n):
    j = i
    # 插入排序
    while j>=gap and alist[j-gap] > alist[j]:
    alist[j-gap], alist[j] = alist[j], alist[j-gap]
    j -= gap
    # 得到新的步长
    gap = gap / 2

    alist = [54,26,93,17,77,31,44,55,20]
    shell_sort(alist)
    print(alist)

    时间复杂度最优时间复杂度:根据步长序列的不同而不同最坏时间复杂度:O(n2)稳定想:不稳定
    归并排序归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组,再合并数组。将数组分解最小之后,然后合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。
    def merge_sort(alist):
    if len(alist) <= 1:
    return alist
    # 二分分解
    num = len(alist)/2
    left = merge_sort(alist[:num])
    right = merge_sort(alist[num:])
    # 合并
    return merge(left,right)

    def merge(left, right):
    ‘’‘合并操作,将两个有序数组left[]和right[]合并成一个大的有序数组’’’
    #left与right的下标指针
    l, r = 0, 0
    result = []
    while l<len(left) and r<len(right):
    if left[l] < right[r]:
    result.append(left[l])
    l += 1
    else:
    result.append(right[r])
    r += 1
    result += left[l:]
    result += right[r:]
    return result

    alist = [54,26,93,17,77,31,44,55,20]
    sorted_alist = mergeSort(alist)
    print(sorted_alist)
    时间复杂度最优时间复杂度:O(nlogn)最坏时间复杂度:O(nlogn)稳定性:稳定

    展开全文
  • 本篇文章讲解三个高级排序算法,分别为希尔排序归并排序、快速排序。虽然它们的思想很复杂,但真的运用得非常得巧妙,我会用丰富的例子以及动图来让大家轻松地理解并掌握。

    本系列文章【数据结构与算法】所有完整代码已上传 github,想要完整代码的小伙伴可以直接去那获取,可以的话欢迎点个Star哦~下面放上跳转链接

    本篇文章来讲解一下更高级的排序算法,顾名思义,它们的排序思想一定更复杂,效率也一定比简单排序更高。为了更方便地理解高级排序算法,还是建议大家先把简单排序了解清楚,因为高级排序也多少借鉴了简单排序的思想,下面放上文章链接

    【数据结构与算法】简单排序(冒泡排序、选择排序、插入排序)完整思路,并用代码封装排序函数

    那么就让我们来了解一下三种高级排序算法吧

    一、希尔排序

    希尔排序是插入排序的改进版本,弥补了插入排序在某些情况下的缺点。

    例如,当长度为100的数组,前面有序区域的数组长度为80,此时我们用第81个数去跟前面有序区域的所有元素比较大小,但恰巧第81个数又是这100个数里最小的,它本应该在索引为1的位置,如图所示

    在这里插入图片描述
    本例中第81个数据的值为1,那么前面有序区域里的80个元素都要往后移动一个位置,这种情况就非常影响排序性能。

    因此,我们就要想办法尽可能早点让小的值靠前,让大的值靠后,这样就能避免上述情况了,这就是希尔排序要解决的问题。

    希尔排序也叫做缩小增量排序,它通过先设置一个增量n,大小为数组长度的一半,将间隔为n的元素视作一个组,然后对每个组内部的元素进行从小到大进行插入排序;然后再将增量n缩小一半,再次进行分组插入排序,直到增量n为1,因为增量为1的时候,所有的元素都为同一个组了


    为了方便大家理解,我用一个例子来展示一个完整的希尔排序过程,首先数据的初始状态如图所示,这里为了更好地体现希尔排序的优点,我特地把值较大的元素放到了靠左的位置,把值较小的元素放到了靠右的位置

    在这里插入图片描述
    该数组长度为8,因此我们设置初始的增量为 8 / 2 = 4,那么该数组的分组情况如下图所示:

    在这里插入图片描述
    图中颜色相同的元素为一组,每组内的各个元素间隔都为4,现在对每个组内进行从小到大排序,排序结果如下图所示:

    在这里插入图片描述
    此时我们将增量缩小一半,即 4 / 2 = 2,同样的,现在将所有元素重新组合,把所有间隔为2的元素视作一组,分组结果如下图所示:

    在这里插入图片描述

    图中颜色相同的元素为一组,每组内的各个元素间隔都为2,现在对每个组内进行从小到大排序,排序结果如下图所示:

    在这里插入图片描述
    我们继续将增量缩小一半,即 2 / 2 = 1,同样的,现在将所有元素重新组合,把所有间隔为1的元素视作一组,此时所有的元素都为同一组了,就相当于对所有的数据进行普通的插入排序,我们可以看到,对比最开始的数据,总得来说,小的值都比较靠左了,大的值也都比较靠右了,这样排序起来效率就很高了。结果如下图所示:

    在这里插入图片描述

    接下来用一个动图,演示一下完整的希尔排序全过程

    在这里插入图片描述
    了解完了希尔排序的实现过程,我们现在用代码来封装一下

    function shellSort(arr) {
        // 1. 获取数组长度
        let length = arr.length
    
        // 2.获取初始的间隔长度
        let interval = Math.floor(length / 2)
    
        // 3. 不断地缩小间隔的大小,进行分组插入排序
        while(interval >= 1) {
    
            // 4. 从 arr[interval] 开始往后遍历,将遍历到的数据与其小组进行插入排序
            for(let i = interval; i < length; i++) {
                let temp = arr[i]
                let j = i
                while(arr[j - interval] > temp && j - interval >= 0) {
                    arr[j] = arr[j - interval]
                    j -= interval 
                }
    
                arr[j] = temp           
            }
    
            // 5. 缩小间隔
            interval = Math.floor(interval / 2)
        }
    
        return arr
    }
    

    来用刚才举得例子来验证一下我们封装的希尔排序是否正确

    let arr = [63, 76, 13, 44, 91, 8, 82, 3]
    let res = shellSort(arr)
    console.log(res)
    /* 打印结果
    [3, 8, 13, 44, 63, 76, 82, 91]
    */
    

    上述情况中,希尔排序最坏情况下的时间复杂度为O(n²)。其实希尔排序的时间复杂度跟增量也有关系,我们上面是通过数组长度一直取一半获取的增量,其实还有一些别的增量规则,可以使得希尔排序的效率更高,例如Hibbard增量序列Sedgewick增量序列,本文就不对这两种增量做过多的讲解了,大家可以去网上搜索一下。

    二、归并排序

    归并排序的实现是使用了一种分而治之的思想,即将一个数组不断地通过两两分组的方式进行比较大小,最后直到所有元素都被分到一组里,那自然就是整体有序的了。

    我们来看一下归并排序的主要思路,首先有如下图所示排列的一组数据:

    在这里插入图片描述
    首先从左往右,每两个元素视为一组,组合前要分别判断一下这两个元素的大小,小的在左,大的右,如图所示

    在这里插入图片描述
    继续再取两个元素组成一组并比较大小,如图所示:

    在这里插入图片描述
    继续上一个步骤,如图所示:

    在这里插入图片描述
    此时,原数组的所有元素都被两两分组完毕了,现在整个数组的长度变成了3,如下图所示:

    在这里插入图片描述
    此时,我们要重新从左向右,每次取两个元素组成一组,同时分别比较两个元素内的所有子元素的大小,因为此时的两个元素内部是有序的,所以我们比较两者大小的话,只需要每次比较数组的第一个元素即可,过程如下图所示:

    在这里插入图片描述
    此时原数组中只剩下一个元素了,所以就不对其做任何组合处理了,此时的数组是这样的:

    在这里插入图片描述
    此时的数组内只有两个元素了,所以我们只需要不断比较两个元素内部的子元素大小,即可获得完整的有序数组了,过程如下图所示:

    在这里插入图片描述
    这就是一个完整的归并排序的过程,接下来我们用代码来实现一下吧

    function mergeSort(arr) {
        
        // 将所有元素不断地两两组合,直到所有元素都被组合成一个组
        while(arr.length > 1){
            // 获取一下遍历前的数组长度,方便下面判断需要组合几次
            let length = arr.length
            
            // 创建空的新数组,用于存放所有组合后的元素
            let next_arr = []
            
            // 取两个元素进行组合,一共取 length / 2 次
            for(let i = 0; i < Math.floor(length / 2); i++){
                // 取出第一个元素
                let left = [].concat(arr.shift())
                // 取出第二个元素
                let right = [].concat(arr.shift())
                // 创建另一个新的空数组,用于存放组合后的所有元素
                let new_arr = []
    
                // 取两个数组中头部最小的值放到新数组中,直到一个数组为空
                while(left.length > 0 && right.length > 0){
                    let min = left[0] > right[0]? right.shift() : left.shift()
                    new_arr.push(min)
                }
                // 将合并好的数组添加到新的数组中
                next_arr.push(new_arr.concat(left.length == 0? right : left))
            }
            // 判断是否有一个未成组的数组
            if(arr.length == 1) next_arr.push(arr[0]);
            
            // 将所有组合后的元素构成的新数组作为下一次遍历的对象
            arr = next_arr
        }
    
        // 返回完整有序数组
        return arr[0]
    }
    

    我们来使用一下该方法,看看是否正确,为了方便大家理解,我在归并排序的函数里加了一条打印的代码,可以看到每次遍历后的数组情况,结果如下

    let arr = [19, 97, 9, 17, 1, 8]
    mergeSort(arr)
    
    /* 打印结果:
    第一次组合后:[ [ 19, 97 ], [ 9, 17 ], [ 1, 8 ] ]
    第二次组合后:[ [ 9, 17, 19, 97 ], [ 1, 8 ] ]
    第三次组合后:[ [ 1, 8, 9, 17, 19, 97 ] ]
    */
    

    查看代码我们不难发现,归并排序运行起来非常得占内存,因为在组合的过程中,我们不断得在创建新的数组,然后又进行合并。但其比较次数却非常得少,只在每次合并元素时进行比较,因此归并排序的效率还是非常得高的。

    三、快速排序

    快速排序相信大家一定不陌生,就算没用过也一定听过,拥有这么大的名声,那么它的排序效率一定很高。而且快速排序也是面试中经常会被问到的,可能会让你当场手写哦~所以大家一定要掌握它的核心思想

    快速排序也用到了分而治之的思想,它的实现思路非常得有意思:

    1. 先选一个元素作为基点pivot
    2. 将其余元素中所有比pivot小的值放到pivot的左边;将所有比pivot大的值放到pivot的右边
    3. 然后分别对pivot左边的所有元素、pivot右边的所有元素从步骤1开始排序依次,直到所有元素完整有序

    思路看着很简单,那么我们来用一个例子具体看一下快速排序的全过程吧

    首先有这样一组数据,如下图所示:

    在这里插入图片描述
    首先我们要选取一个元素作为基点pivot,最后排序完后,pivot左边的所有元素都是小于pivot的,右边的所有元素都是大于pivot的,因此我们希望的是尽量是两边平均一下,所以这里将采用一种方式寻找到一个大概的中点,即取数组两头的索引,分别为left 、right,再取一个中点 center,结果如下图:

    在这里插入图片描述

    然后在这三个元素中找到一个中等大小的值,并将其放到数组的开头位置,如下图所示:

    在这里插入图片描述

    到此,我们就可以将该数组的第一个元素作为此次遍历的基点pivot了,同时,我们将引入两个指针,即 ij,分别指向 left 和 right,如图所示

    在这里插入图片描述

    接下来就可以进行遍历了,这里我们把遍历过程称为填坑法,因为现在我们取到了数组的第一个值为pivot,所以可以假设这个位置上没有元素了,留了一个坑,需要我们将别的元素填进来。所以我们要从指针 j 开始往右寻找到一个比pivot小的值,若找到了,则将找到的值填到坑里,但要注意的是,指针 j 不能找到 指针 i 的左边去,即当指针 j 与 指针 i 重合时就停止移动。

    过程如下图所示:

    在这里插入图片描述

    此时我们可以看到,指针 j 找到了一个小于pivot的值 8,并将找到的值填到了坑里,那么此时指针 j 所指向的位置就留下了一个坑,又需要别的元素来填坑,所以此时我们就要让指针 i 向右找一个大于pivot的值,并将值填到坑里,同样的,指针 i 也不能找到指针 j 的右边,即当指针 i 与 指针 j 重合时就停止移动。

    过程如下图所示:

    在这里插入图片描述

    指针 i 找到了一个大于pivot的值 97 并将其填到了坑里,此时指针 i 所在的位置就留下了一个坑,因此我们又要让指针 j 往左找小于pivot的值并填到坑里,过程如图所示:

    在这里插入图片描述

    紧接着,指针 i 又要向右找大于pivot的值,但是移动了两个位置都没有找到,并且此时指针 i 指针 j 重合了,此时我们只需要将pivot填入到坑里就实现了pivot左边的所有元素小于它,右边所有的元素都大于它了,如图所示:

    在这里插入图片描述

    接下来的操作,就是我们要单独对此时pivot的左边所有元素和右边的所有元素进行上述的一系列操作,就可以实现快速排序了。本例中的左右两边区域的元素个数都是小于等于3个的,因此直接将这几个值互相进行比较大小比较方便,过程如下图:

    在这里插入图片描述

    了解了快速排序的实现思路,我们来用代码来实现一下

    function quickSort(arr) {
        // 两个数据进行交换
        function exchange(v1, v2) {
            let temp = arr[v1]
            arr[v1] = arr[v2]
            arr[v2] = temp
        }
        
        // 找到相对合适的元素放到数组索引为0的位置作为基点pivot
        function init(left, right) {
            let center = Math.floor((left + right) / 2)
    
            // 比较索引为left、center、right三个值的大小,从小到大排列
            if(arr[left] > arr[right]) exchange(left, right)
            if(arr[center] > arr[right]) exchange(center, right)
            if(arr[left] > arr[center]) exchange(left, center)
    
            // 判断数组长度是否大于3,若小于3,则数组已经排序好了,不需要做任何处理
            if(right - left > 2) exchange(left, center)
        }
    
        function quick(left, right) {
            init(left, right)
            // 若数组长度小于等于2,则不需要做任何操作了,因为init函数已经排序好了
            if(right - left <= 2) return;
            
            // 创建指针i和j,分别指向left和right
            let i = left
            let j = right
            // 将该数组区域的第一个元素作为基点pivot
            let pivot = arr[i]
    
            // 不断让指针i和j寻找合适的值填坑,直到两个指针重合
            while(i < j) {
                // 指针j不断向左找小于pivot的值,但指针j不能找到指针i的左边
                while(arr[j] > pivot && j > i) {
                    j --
                }
                // 将找到的小于pivot的值填到指针i所指向的坑中
                arr[i] = arr[j]
    
                // 指针i不断向右找大于pivot的值,但指针i不能找到指针j的右边
                while(arr[i] < pivot && i < j) {
                    i ++
                }
                // 将找到的大于pivot的值填到指针j所指向的坑中
                arr[j] = arr[i]
            }
    
            // 将pivot填到指针i和指针j共同指向的坑中
            arr[i] = pivot
    
            // 对此时pivot的左边所有元素进行快排
            quick(left, i - 1)
            // 对此时pivot的右边所有元素进行快排
            quick(i + 1, right)
        }
    
        quick(0, arr.length - 1)
    
        return arr  
    }
    

    我们可以简单来验证一下快速排序的正确性

    let arr = [19, 97, 9, 17, 8, 1]
    console.log(quickSort(arr))
    /* 打印结果为:
    	[1, 8, 9, 17, 19, 97]
    */
    

    四、结束语

    排序算法中的高级排序(希尔排序、归并排序、快速排序)就已经讲完啦,下一篇文章为动态规划

    大家可以关注我,之后我还会一直更新别的数据结构与算法的文章来供大家学习,并且我会把这些文章放到【数据结构与算法】这个专栏里,供大家学习使用。

    然后大家可以关注一下我的微信公众号:前端印象,等这个专栏的文章完结以后,我会把每种数据结构和算法的笔记放到公众号上,大家可以去那获取。

    或者也可以去我的github上获取完整代码,欢迎大家点个Star

    我是Lpyexplore,一个因Python爬虫而进入前端的探索者。创作不易,喜欢的加个关注,点个收藏,给个赞~

    展开全文
  • 以下列出了数据结构算法的八种基本排序:插入排序 冒泡排序 选择排序 高速排序 堆排序 归并排序 基数排序 希尔排序,然后是測试的样例。代码位置:http://download.csdn.net/detail/luozuolincool/8040027 排序类...
    C# 插入排序 冒泡排序 选择排序 高速排序 堆排序 归并排序 基数排序 希尔排序
    以下列出了数据结构与算法的八种基本排序:插入排序 冒泡排序 选择排序 高速排序 堆排序 归并排序 基数排序 希尔排序,然后是測试的样例。代码位置:http://download.csdn.net/detail/luozuolincool/8040027
    排序类:
    public class Sortings
        {
            //插入排序
            public void insertSort(int[] array)
            {
                int temp = 0;
                int index = 0;
                for (int i = 0; i < array.Length; i++)
                {
                    for (int j = 0; j < i; j++)
                    {
                        if (array[i] < array[j])//从j到i之间的数总体右移动。将i数据放到j位置
                        {
                            index = i;
                            temp = array[i];
                            while (index > j)
                            {
                                array[index] = array[index - 1];
                                index--;
                            }
                            array[j] = temp;
                            break;
                        }
                    }
                }
                printArray(array, "插入排序:");
            }
            public void printArray(int[] array, String type)
            {
                Console.WriteLine(type);
                for (int i = 0; i < array.Length; i++)
                {
                    Console.Write(array[i] + ",");
                }
                Console.WriteLine();
            }
            //冒泡排序
            public void bubbleSort(int[] array)
            {
                int temp = 0;
                bool exchanged = true;
                for (int i = 0; i < array.Length; i++)
                {
                    if (!exchanged)
                        break;
                    for (int j = array.Length - 1; j > i; j--)
                    {
                        exchanged = false;
                        if (array[j] < array[j - 1])//后面的数比前面的小就交换
                        {
                            temp = array[j];
                            array[j] = array[j - 1];
                            array[j - 1] = temp;
                            exchanged = true;
                        }
                    }
                }
                printArray(array, "冒泡排序:");
            }
            //选择排序:从前到后依次选择最小的放在最前面,第二小的放在第二个位置
            public void selectionSort(int[] array)
            {
                int minIndex = 0;
                int temp = 0;
                for (int i = 0; i < array.Length; i++)
                {
                    minIndex = i;
                    for (int j = i; j < array.Length; j++)
                    {
                        if (array[j] < array[minIndex])
                            minIndex = j;
                    }
                    //将i到j之间最小的数放到位置i
                    temp = array[minIndex];
                    array[minIndex] = array[i];
                    array[i] = temp;
                }
                printArray(array, "选择排序:");
            }
            //高速排序
            public void quickSort(int[] array)
            {
                quicksort1(array, 0, array.Length - 1);
                printArray(array, "高速排序:");
            }
            public void quicksort1(int[] array, int start, int end)
            {
                if (start >= end)
                    return;
                int i = start, j = end;
                int k = array[i];
                while (i < j)
                {
                    while (array[j] >= k && i < j)
                        j--;
                    array[i] = array[j];
                    while (array[i] < k && i < j)
                        i++;
                    array[j] = array[i];
                }
                array[i] = k;
                quicksort1(array, start, i -1);
                quicksort1(array, i +1, end);
            }
            //堆排序
            public void stackSort(int[] array)
            {
                MyHeap h = new MyHeap();
                h.buildHeap(array);
                h.HeapSort();
                h.printHeap();
            }
            //归并排序
            public void mergeSort(int[] array)
            {
                mergeSort1(array, 0, array.Length - 1);
                printArray(array, "归并:");
            }
            private void mergeSort1(int[] array ,int start,int end)
            {
                if (start >= end)
                    return;
                mergeSort1(array, start, (start+end) / 2);
                mergeSort1(array, (start + end) / 2+1,end);
                merge(array, start, (start + end) / 2, end);
                
            }
            private void merge(int[] array,int start,int mid,int end)
            {
                Queue<int> q = new Queue<int>();
                int i = start, j = mid + 1;
                while (i <=mid && j <=end)
                {
                    if (array[i] < array[j])
                    {
                        q.Enqueue(array[i]);
                        i++;
                    }
                    else
                    {
                        q.Enqueue(array[j]);
                        j++;
                    }
                }
                while (i <= mid)
                    q.Enqueue(array[i++]);
                while (j <= end)
                    q.Enqueue(array[j++]);
               
                for (i = start; i <= end; i++)
                    array[i] = q.Dequeue();
            }
            //基数排序
            public void radixSort(int[] array)
            {
                int maxlength=0;//数据最大位数
                //申请空间用于存放数据
                List<List<int>> lists=new List<List<int>>();
                //申请10个桶,用于存放0-9
                for (int i = 0; i < 10; i++)
                    lists.Add(new List<int>());
                //获取数据的最大位数
                for (int i = 0; i < array.Length; i++)
                    maxlength = maxlength < array[i].ToString().Length ?

    array[i].ToString().Length : maxlength;
                for (int i = 0; i < maxlength; i++)
                {
                    //数据入桶
                    for (int j = 0; j < array.Length; j++)
                    {
                        lists[array[j] / (int)(Math.Pow(10, i)) - array[j] / (int)(Math.Pow(10, i+1))*10].Add(array[j]);
                    }
                    int t = 0;
                    //将桶里面的数据又一次放入数组
                    for (int k = 0; k < 10; k++)
                    {
                        
                        foreach (int item in lists[k])
                            array[t++] = item;
                    }
                    //清空桶里面的数据
                    for (int k = 0; k < 10; k++)
                    {
                        lists[k].Clear();
                    }


                }
                printArray(array, "基数排序");
            }
            //希尔排序
            public void shellSort(int[] array)
            {
                int step = array.Length / 2;
                while (step > 0)
                {
                    shellInsert(array, step);
                    Console.WriteLine();
                    printArray(array, "希尔");
                    step = step / 2;
                }
                printArray(array, "希尔");
            }
            private void shellInsert(int[] array,int step)
            {
                int temp = 0;
                int index = 0;
                for (int i = 0; i < array.Length; i=i+step)
                {
                    for (int j = 0; j < i; j=j+step)
                    {
                        if (array[i] < array[j])//从j到i之间的数总体右移动,将i数据放到j位置
                        {
                            index = i;
                            temp = array[i];
                            while (index > j)
                            {
                                array[index] = array[index - 1];
                                index--;
                            }
                            array[j] = temp;
                            break;
                        }
                    }
                }
            }
        }

    測试代码:
     static void Main(string[] args)
            {
                int[] array = { 12,3,23,4,21,44,2,3,11};
                Console.WriteLine("待排序数组:");
                for (int i = 0; i < array.Length; i++)
                {
                    Console.Write(array[i]+",");
                }
                Console.WriteLine();
               // insertSort(array);
               // bubbleSort(array);
               // selectionSort(array);
              //  (new Sortings()).quickSort(array);
              //  (new Sortings()).stackSort(array);
               // (new Sortings()).mergeSort(array);
                //(new Sortings()).shellSort(array);
                (new Sortings()).radixSort(array);
                Console.Read();
            }

    转载于:https://www.cnblogs.com/jhcelue/p/7016756.html

    展开全文
  • 下面列出了数据结构算法的八种基本排序:插入排序 冒泡排序 选择排序 快速排序 堆排序 归并排序 基数排序 希尔排序,然后是测试的例子
  • 目录归并排序基本思想算法实现快速排序基本思想算法实现希尔排序基本思想算法实现简单测试(JUnit)源码 归并排序 归并排序归并排序(Merge Sort)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法...
  • 1、树二叉树 (1)二叉树   (2)二叉树的存储方式 (3)二叉树小结 2、堆  (1)什么是堆  (2)调整 3、堆排序的过程    (1)构造堆 市长 镇长 村长 ...
  • 数据结构算法-冒泡排序,选择排序,插入排序,希尔排序,快速排序,基数排序,归并排序,堆排序
  • 005数据结构与算法Python排序与搜索排序算法的稳定性冒泡排序冒泡排序的分析代码实现时间复杂度选择排序选择排序分析代码实现时间复杂度插入排序代码实现时间复杂度快速排序(工作中常用)代码实现希尔排序希尔排序...
  • 本篇博客主要巩固算法第四版第二章的排序算法——选择排序,插入排序,希尔排序归并排序,快速排序。讲解它们的思想,原理、算法的实现以及这些算法的性能,希望能帮助大家快速理解并掌握它们。 二、排序算法详解...
  • 第一类:插入排序、冒泡排序、选择排序 它们比较相邻的元素,平均算法时间代价都为O(n2); 插入排序: public class insertion_sort { public static void insertsort(int[] unsorted){ for(int i=1;i;i++){ ...
  • (1)选择排序public class Sortexample { public void exch(int[] a,int i,int j){ int temp = a[i]; a[i] = a[j]; a[j] = temp; } public void selection(int[] a){ int len
  • 1. 前言 算法为王。 想学好前端,先练好内功,只有...之所以把归并排序、快速排序、希尔排序、堆排序放在一起比较,是因为它们的平均时间复杂度都为O(nlogn)。 请大家带着问题:快排和归并用的都是分治思想...
  • 文章详细总结了插入排序、希尔排序、选择排序、归并排序、交换排序(冒泡排序、快速排序)、基数排序、外部排序。从`思想`到`代码实现`。 大三党,大数据专业,正在为面试准备,欢迎学习交流`。
  • 这里写目录标题选择排序冒泡排序插入排序希尔排序归并排序快速排序 选择排序 常规思维: 第一步 先找出最大数,最后一个数交换。 第二步 再找出除最后一个最大数,倒数第二个交换位置。 。。。 。。。重复...
  • 希尔排序与归并排序

    2019-11-18 20:01:20
    非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。 算法复杂度 相关概念 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b...
  • 希尔排序 希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。 希尔排序是把记录按下标的一定...
  • (1)插入排序:直接插入排序、希尔排序 (2)选择排序:简单选择排序、堆排序 (3)交换排序:冒泡排序、快速排序 (4)归并排序、基数排序 我们先回顾知识点:时间复杂度 时间频度:一个算法花费的时间算法...
  • 希尔排序 # coding:utf-8 def shell_sort(alist): """希尔排序""" n = len(alist) gap = n // 2 # gap 变化到0之前,插入算法执行的次数 while gap >= 1: # 插入算法普通的插入算法的区别 就是gap...
  • 希尔排序三.快速排序四.归并排序五.计数排序 一.插入排序 当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排序码array[i-1],array[i-2],…的排序码顺序进行比较...
  • 快快速速排排序序冒冒泡泡排排序序桶桶排排序序基基数数排排序序堆堆排排 序序希希尔尔排排序序归归并并排排序序计计数数排排序序 这篇文章主要介绍了10个python3常用排序算法详细说明实例,需要的朋友可以参考下 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,351
精华内容 540
关键字:

归并排序与希尔排序