快速搞定8大排序算法

我遇到过那些人那些事,还有,我希望遇见你

点击上方蓝字“在北方玩弹子球”一起玩耍

插入排序

  • 基本思想:每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。
  • 算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。
  • 代码:
        public static void insertionSort(int[] array){
                int tmp;
                for(int i=1;i<array.length;i++){
                    tmp = array[i];  //将当前位置的数给tmp
                    int j = i;
                    for(;j>0&&array[j-1]>tmp;j--){
                        /*                         * 往右移,腾出左边的位置,                         * array[j-1]>tmp:大于号是升序排列,小于号是降序排列                         */
                        array[j] = array[j-1];
                    }
                    //将当前位置的数插入到合适的位置
                    array[j] = tmp;
                }
            }

冒泡排序

  • 基本思想:持续比较相邻的元素。如果第一个比第二个大,就交换他们两个。直到没有任何一对数字需要比较。
  • 冒泡排序最好的时间复杂度为O(n)。冒泡排序的最坏时间复杂度为O(n^2)。因此冒泡排序总的平均时间复杂度为O(n^2)。
  • 算法适用于少量数据的排序,是稳定的排序方法。
  • 代码:
    public static void bubbleSort(int[] array){
            int tmp;
            boolean flag = false;  //设置是否发生交换的标志
            for(int i = array.length-1;i >= 0;i--){
                for(int j=0;j<i;j++){          //每一轮都找到一个最大的数放在右边
                    if(array[j]>array[j+1]){
                        tmp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = tmp;
                        flag = true;   //发生了交换
                    }
                }
                if(!flag)  break;   //这一轮循环没有发生交换,说明排序已经完成,退出循环
            }
        }

选择排序

  • 基本思想:每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
  • 选择排序是不稳定的排序方法。时间复杂度 O(n^2)。
  • 代码:
public static void selectSort(int[] array){
        for(int i = 0;i<array.length-1;i++){
            int min = array[i];
            int minindex = i;
            for(int j = i;j<array.length;j++){
                if(array[j]<min){  //选择当前最小的数
                    min = array[j];
                    minindex = j;
                }
            }
            if(i != minindex){ //若i不是当前元素最小的,则和找到的那个元素交换
                array[minindex] = array[i];
                array[i] = min;
            }
        }
    }

希尔排序

  • 基本思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
  • 在使用增量dk的一趟排序之后,对于每一个i,我们都有a[i]<=a[i+dk],即所有相隔dk的元素都被排序。
  • 希尔排序不稳定,时间复杂度 平均时间 O(nlogn) 最差时间O(n^2)
  • 代码:
    public static void shellSort(int[] array){
            int j;
            for(int gap = array.length/2; gap>0; gap /= 2){
                //定义一个增长序列,即分割数组的增量,d1=N/2   dk=(d(k-1))/2
                for(int i = gap; i<array.length;i++){
                    int tmp = array[i];
                    for( j =i; j>=gap&&tmp<array[j-gap]; j -= gap){
                        //将相距为Dk的元素进行排序
                        array[j] = array[j-gap];
                    }
                    array[j] = tmp;
                }
            }
        }

堆排序

  • 预备知识:
    • 二叉堆是完全二元树(二叉树)或者是近似完全二元树(二叉树)。 二叉堆有两种:最大堆和最小堆。 大根堆:父结点的键值总是大于或等于任何一个子节点的键值; 小根堆:父结点的键值总是小于或等于任何一个子节点的键值。 二叉堆一般用数组来表示。例如,根节点在数组中的位置是0,第n个位置的子节点分别在2n+1和 2n+2。因此,第0个位置的子节点在1和2,1的子节点在3和4。以此类推。这种存储方式便於寻找父节点和子节点。 例如初始要排序的数组为:49, 38, 65, 97, 76, 13, 27, 49 构造成大根堆之后的数组为:97 76 65 49 49 13 27 38 实际树形结构如图(最大堆):
  • 堆排序基本思想:在排序过程中,将R[l..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】,在当前无序区中选择关键字最大(或最小)的记录。堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
  • 堆排序是一种选择排序,其时间复杂度为O(nlogn)。堆排序是不稳定的
  • 代码:
/*         * 堆排序         * 调整最大堆,交换根元素和最后一个元素。         * 参数说明:         *     a -- 待排序的数组         */
        public static void heapSort(int[] a) {
            int n = a.length;
            int i,tmp;
            // 从(n/2-1) --> 0逐次遍历。遍历之后,得到的数组实际上是一个(最大)二叉堆。
            for (i = n / 2 - 1; i >= 0; i--)
                maxHeapDown(a, i, n-1);
            // 从最后一个元素开始对序列进行调整,不断的缩小调整的范围直到第一个元素
            for (i = n - 1; i > 0; i--) {
                // 交换a[0]和a[i]。交换后,a[i]是a[0...i]中最大的。
                tmp = a[0];
                a[0] = a[i];
                a[i] = tmp;
                // 调整a[0...i-1],使得a[0...i-1]仍然是一个最大堆。
                // 即,保证a[i-1]是a[0...i-1]中的最大值。
                maxHeapDown(a, 0, i-1);
            }
        }
        /*         * 注:数组实现的堆中,第N个节点的左孩子的索引值是(2N+1),右孩子的索引是(2N+2)。         *     其中,N为数组下标索引值,如数组中第1个数对应的N为0。         *         * 参数说明:         *     a -- 待排序的数组         *     start -- 被下调节点的起始位置(一般为0,表示从第1个开始)         *     end   -- 截至范围(一般为数组中最后一个元素的索引)         */
        public static void maxHeapDown(int[] a, int start, int end) {
            int c = start;            // 当前(current)节点的位置
            int l = 2*c + 1;        // 左(left)孩子的位置
            int tmp = a[c];            // 当前(current)节点的大小
            for (; l <= end; c=l,l=2*l+1) {
                // "l"是左孩子,"l+1"是右孩子
                if ( l < end && a[l] < a[l+1])
                    l++;        // 左右两孩子中选择较大者,即m_heap[l+1] 
                if (tmp >= a[l])
                    break;        // 调整结束
                else {            // 交换值
                    a[c] = a[l];
                    a[l]= tmp;
                }
            }
        }

归并排序

  • 归并排序的原理:
    • 将待排序的数组分成前后两个部分,再递归的将前半部分数据和后半部分的数据各自归并排序,得到的两部分数据,然后使用merge合并算法(算法见代码)将两部分算法合并到一起。 例如:如果N=1;那么只有一个数据要排序,N=2,只需要调用merge函数将前后合并,N=4,........... 也就是将一个很多数据的数组分成前后两部分,然后不断递归归并排序,再合并,最后返回有序的数组。
  • 归并排序的时间复杂度:
    • 归并排序的最好、最坏和平均时间复杂度都是O(nlogn),而空间复杂度是O(n),比较次数介于(nlogn)/2和(nlogn)-n+1,赋值操作的次数是(2nlogn)。因此可以看出,归并排序算法比较占用内存,但却是效率高且稳定的排序算法。
  • 代码:
 public class MergeSort {
        private static void mergeSort(int[] array,int[] tmp,int left,int right){
            if(left<right){
                int center = ( left + right ) / 2;//取数组的中点
                mergeSort(array,tmp,left,center);//归并排序数组的前半部分
                mergeSort(array,tmp,center+1,right);//归并排序数组的后半部分
                merge(array,tmp,left,center+1,right);//将数组的前后半部分合并
            }
        }
        /*         * 超简单的合并函数         */
        private static void merge(int[] array, int[] tmp, int leftPos, int rightPos, int rightEnd) {
            // TODO Auto-generated method stub
            int leftEnd = rightPos - 1;
            int tmpPos = leftPos;
            int numElements = rightEnd - leftPos + 1;
            while(leftPos <= leftEnd && rightPos <= rightEnd){
                if(array[leftPos]<=array[rightPos]){
                    tmp[tmpPos++] = array[leftPos++];
                }else{
                    tmp[tmpPos++] = array[rightPos++];
                }
            }
            while(leftPos <= leftEnd){
                tmp[tmpPos++] = array[leftPos++];
            }
            while(rightPos <= rightEnd){
                tmp[tmpPos++] = array[rightPos++];
            }
            for(int i=0;i<numElements;i++,rightEnd--){
                array[rightEnd] = tmp[rightEnd];
            }
        }
        public static void mergeSort(int[] array){
            int[] tmp = new int[array.length];//声明一个用来合并的数组
            mergeSort(array,tmp,0,array.length-1);//调用排序函数,传入数字的起点和终点
        }
    }

快速排序

  • 快速排序原理:
  1. 如果数组S中元素是0或者1,则返回;
  2. 区数组S中任一元素v,称之为枢纽元;
  3. 将S-{v}(S中剩余的元素)划分成连个不相交的集合:S1={S-{v}|x<=v}和S2={S-{v}|x>=v};
  4. 返回{quicksort(s1)}后跟v,继而返回{quicksort(S2)}。
  • 选取枢纽元(三数中值分割法)
    • 一般的做法是使用左端、右端和中心位置上的三个元素的中值作为基元。 分割策略: 在分割阶段吧所有小元素移到数组的左边,大元素移到数组右边。,大小是相对于枢纽元素而言的。 当i在j的左边时,将i右移,移过哪些小于枢纽元的元素,并将j左移,已过那些大于枢纽元的元素,当i和j停止时,i指向一个大元素,而j指向一个小元素,如果i在j的左边,那么将这两个元素交换,其效果是把一个大元素推向右边,而把小元素推向左边。
  • 速排序平均时间复杂度为O(nlogn),最坏情况为O(n^2),n越大,速度越快。不是稳定的排序算法。
  • 代码:
/*     * 快速排序     * 两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],     * 其中center_index是中枢元素的数组下标,而右边的j下标一直往左走,当a[j] > a[center_index]     * 如果i和j都走不动了,i <= j, 交换a[i]和a[j],重复上面的过程,直到i>j     * 交换a[j]和a[center_index],完成一趟快速排序     * 枢轴采用三数中值分割法可以优化     */
    //递归快速排序
    public static void quickSort(int a[]){
        qSort(a, 0, a.length - 1);
    }
    //递归排序,利用两路划分
    public static void qSort(int a[],int low,int high){
        int pivot = 0;
        if(low < high){
            //将数组一分为二
            pivot = partition(a,low,high);
            //对第一部分进行递归排序
            qSort(a,low,pivot);
            //对第二部分进行递归排序
            qSort(a,pivot + 1,high);
        }
    }
    //partition函数,实现三数中值分割法
    public static int partition(int a[],int low,int high){
        int pivotkey = a[low];   //选取第一个元素为枢轴记录
        while(low < high){
            //将比枢轴记录小的交换到低端
            while(low < high && a[high] >= pivotkey){
                high--;
            }
            //采用替换而不是交换的方式操作
            a[low] = a[high];
            //将比枢轴记录大的交换到高端
            while(low < high && a[low] <= pivotkey){
                low++;
            }
            a[high] = a[low];
        }
        //枢纽所在位置赋值
        a[low] = pivotkey;
        //返回枢纽所在的位置
        return low;
    }

桶式排序

  • 桶式排序不再是一种基于比较的排序方法,它是一种比较巧妙的排序方式,但这种排序方式需要待排序的序列满足以下两个特征: 待排序列所有的值处于一个可枚举的范围之类; 待排序列所在的这个可枚举的范围不应该太大,否则排序开销太大。
  • 排序的具体步骤如下:
    • (1)对于这个可枚举范围构建一个buckets数组,用于记录“落入”每个桶中元素的个数;
    • (2)将(1)中得到的buckets数组重新进行计算,按如下公式重新计算: buckets[i] = buckets[i] +buckets[i-1] (其中1<=i<buckets.length);
  • 桶式排序是一种非常优秀的排序算法,时间效率极高,它只要通过2轮遍历:第1轮遍历待排数据,统计每个待排数据“落入”各桶中的个数,第2轮遍历buckets用于重新计算buckets中元素的值,2轮遍历后就可以得到每个待排数据在有序序列中的位置,然后将各个数据项依次放入指定位置即可。
  • 桶式排序的空间开销较大,它需要两个数组,第1个buckets数组用于记录“落入”各桶中元素的个数,进而保存各元素在有序序列中的位置,第2个数组用于缓存待排数据.
  • 桶式排序是稳定的。如果待排序数据的范围在0~k之间,那么它的时间复杂度是O(k+n)的.
  • 但是它的限制多,比如它只能排整形数组。而且当k较大,而数组长度n较小,即k>>n时,辅助数组C[k+1]的空间消耗较大。当数组为整形,且k和n接近时, 可以用此方法排序。
  • 代码实现:
//min的值为0,max的值为待排序数组中最大值+1
        public static void bucketSort(int[] data, int min, int max) {  
            // 缓存数组  
            int[] tmp = new int[data.length];  
            // buckets用于记录待排序元素的信息  
            // buckets数组定义了max-min个桶  
            int[] buckets = new int[max - min];  
            // 计算每个元素在序列出现的次数  
            for (int i = 0; i < data.length; i++) {  
                buckets[data[i] - min]++;  
            }  
            // 计算“落入”各桶内的元素在有序序列中的位置  
            for (int i = 1; i < max - min; i++) {  
                buckets[i] = buckets[i] + buckets[i - 1];  
            }  
            // 将data中的元素完全复制到tmp数组中  
            System.arraycopy(data, 0, tmp, 0, data.length);  
            // 根据buckets数组中的信息将待排序列的各元素放入相应位置  
            for (int k = data.length - 1; k >= 0; k--) {  
                data[--buckets[tmp[k] - min]] = tmp[k];  
            }  
        }

总结

  • 下面是一个总的表格,大致总结了我们常见的所有的排序算法的特点。
  • 性能测试

原文发布于微信公众号 - 轮子工厂(Programmer-ing)

原文发表时间:2018-03-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏苦逼的码农

从0打卡leetcode之day9--字符串转整型

好久没更新了,今天是开学的第一天,这学期选了门算法的课,打算好好刷下《算法导论》这本书,可能接下来会一边分享leetcode的刷题贴,一边分享自己在书上所学的一...

903
来自专栏数据小魔方

左手用R右手Python系列7——排序

排序可能是日常数据清洗过程中比较高频的应用了,今天这一篇给大家介绍R语言和Python中最为常见的排序函数应用。 R语言: sort order rank ar...

2824
来自专栏郭耀华‘s Blog

十大经典排序算法最强总结(含JAVA代码实现)

最近几天在研究排序算法,看了很多博客,发现网上有的文章中对排序算法解释的并不是很透彻,而且有很多代码都是错误的,例如有的文章中在“桶排序”算法中对每个桶进行排...

4767
来自专栏微信公众号:Java团长

十大经典排序算法最强总结(含Java代码实现)

常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里,元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较,才能确定自己的位...

3341
来自专栏小樱的经验随笔

Codeforces Round #410 (Div. 2)(A,字符串,水坑,B,暴力枚举,C,思维题,D,区间贪心)

A. Mike and palindrome time limit per test:2 seconds memory limit per test:256 m...

4754
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-day09-重构随机点名器

Java基础-day09-重构随机点名器 1.案例介绍与演示 随机点名的案例由之前简单的Person对象,重构为相对完整的Person对象并使用。 2.案例回顾...

4566
来自专栏zhisheng

Java常用排序算法/程序员必须掌握的8大排序算法

Java常用排序算法/程序员必须掌握的8大排序算法 分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排...

5078
来自专栏magicsoar

Effective Modern C++翻译(2)-条款1:明白模板类型推导

第一章 类型推导 C++98有一套单一的类型推导的规则:用来推导函数模板,C++11轻微的修改了这些规则并且增加了两个,一个用于auto,一个用于decltyp...

19010
来自专栏自学笔记

Sort Algorithm排序算法

第一次迭代,寻找0到6个下标的数字哪个是最小的,找到最小的就和第一个交换,也就是2。第一次遍历所有

1002
来自专栏ACM算法日常

基础算法|7 希尔排序 HDU 1425

我们从最初的冒泡排序算法,到上篇文章的折半插入排序算法,我们一共学习了5种排序算法,相信以大家的聪明才智肯定都消化了^_^。在本篇文章中,我们又将学习第6种排序...

922

扫码关注云+社区

领取腾讯云代金券