精华内容
下载资源
问答
  • 十大排序算法

    万次阅读 多人点赞 2021-08-20 13:37:46
    冒泡排序 从数组头开始,比较相邻的元素。如果第一个比第二个大(小),就交换它们两个 对每一对相邻元素作同样的工作,从开始第一对到尾部的最后一对,这样在最后的元素应该会是最大(小)的数 重复步骤1~2,重复次数...

    有人问动图怎么做的,动图不是我做的哦,静图才是,推荐几个动画演示的网站:

    冒泡排序

    1. 从数组头开始,比较相邻的元素。如果第一个比第二个大(小),就交换它们两个
    2. 对每一对相邻元素作同样的工作,从开始第一对到尾部的最后一对,这样在最后的元素应该会是最大(小)的数
    3. 重复步骤1~2,重复次数等于数组的长度,直到排序完成

    image-20210728113340011

    代码实现

    对下面数组实现排序:{24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9}

    代码实现

    public class BubbleSort {
    
        public static final int[] ARRAY = {24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9};
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    
        public static int[] sort(int[] array) {
            if (array.length == 0) {
                return array;
            }
            for (int i = 0; i < array.length; i++) {
                //array.length - 1 -i 已经冒泡到合适位置无需在进行排序,减少比较次数
                for (int j = 0; j < array.length - 1 -i; j++) {
                    //前面的数大于后面的数交换
                    if (array[j + 1] < array[j]) {
                        int temp = array[j + 1];
                        array[j + 1] = array[j];
                        array[j] = temp;
                    }
                }
            }
            return array;
        }
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    }
    

    时间复杂度

    对于上面12个数据项,从第一个元素开始,第一趟比较了11次,第二趟比较了10次,依次类推,一直到最后一趟,就是:

    11 + 10 + 9 + 8 + 7 + 6 + 5  + 4 + 3  + 2 + 1  =  66次
    

    若有n个元素,则第一趟比较为(n-1)次,第二趟比较为(n-2)次,依次类推:

    (n-1) + (n-2) + (n-3) + ...+ 2 + 1 = n * (n-1)/2
    

    在大O表示法中,去掉常数系数和低阶项,该排序方式的时间复杂度为:O(n2)

    算法稳定性

    假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。——百度百科

    在代码中可以看到,array[j + 1] = array[j]的时候,我们可以不移动array[i]array[j],所以冒泡排序是稳定的

    选择排序

    1. 找到数组中最大(或最小)的元素
    2. 将它和数组的第一个元素交换位置(如果第一个元素就是最大(小)元素那么它就和自己交换)
    3. 在剩下的元素中找到最大(小)的元素,将它与数组的第二个元素交换位置。如此往复,直到将整个数组排序。

    image-20210728144443166

    代码实现

    对下面数组实现排序:{87, 23, 7, 43, 78, 62, 98, 81, 18, 53, 73, 9}

    动图演示

    选择排序

    代码实现

    public class SelectionSort {
    
        public static final int[] ARRAY = {87, 23, 7, 43, 78, 62, 98, 81, 18, 53, 73, 9};
    
        public static int[] sort(int[] array) {
            if (array.length == 0) {
                return array;
            }
            for (int i = 0; i < array.length; i++) {
                //最小数的下标,每个循环开始总是假设第一个数最小
                int minIndex = i;
                for (int j = i; j < array.length; j++) {
                    //找到最小索引
                    if (array[j] < array[minIndex]) {
                        //保存最小索引
                        minIndex = j;
                    }
                }
                //最小索引的值
                int temp = array[minIndex];
                array[minIndex] = array[i];
                array[i] = temp;
            }
            return array;
        }
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    }
    

    时间复杂度

    很明显,和冒泡排序相比,在查找最小(或最大)元素的索引,比较次数仍然保持为O(n2)

    ,但元素交换次数为O(n)

    算法稳定性

    选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果一个元素比当前元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。举个例子,数组5,8,5,2,9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中两个5的相对前后顺序就被破坏了,所以选择排序是一个不稳定的排序算法

    image-20210728144637093

    插入排序

    当我们在玩扑克牌的时候,总是在牌堆里面抽取最顶部的一张然后按顺序在手中排列。

    插入排序是指在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。

    1. 对于未排序数据(一般取数组的二个元素,把第一个元素当做有序数组),在已排序序列中从左往右扫描,找到相应位置并插入。
    2. 为了给要插入的元素腾出空间,需要将插入位置之后的已排序元素在都向后移动一位。

    image-20210728162127494

    代码实现

    对下面数组实现排序:{15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1}

    动图演示

    插入排序

    代码实现

    public class InsertionSort {
    
        public static final int[] ARRAY = {15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1};
    
        public static int[] sort(int[] array) {
            if (array.length == 0) {
                return array;
            }
            //待排序数据,改数据之前的已被排序
            int current;
            for (int i = 0; i < array.length - 1; i++) {
                //已被排序数据的索引
                int index = i;
                current = array[index + 1];
                //将当前元素后移一位
                while (index >= 0 && current < array[index]) {
                    array[index + 1] = array[index];
                    index--;
                }
                //插入
                array[index + 1] = current;
            }
            return array;
        }
    
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    }
    

    时间复杂度

    在上面图示中,第一趟循环比较一次,第二趟循环两次,依次类推,则最后一趟比较n-1次:

    1 + 2 + 3 +… + n-1 = n*(n-1)/2
    

    也就是说,在最坏的情况下(逆序),比较的时间复杂度为O(n2)

    在最优的情况下,即while循坏总是假的,只需当前数跟前一个数比较一下就可以了,这时一共需要比较n-1次,时间复杂度为O(n)

    算法稳定性

    在比较的时候,过两个数相等的话,不会进行移动,前后两个数的次序不会发生改变,所以插入排序是稳定的

    希尔排序

    一种基于插入排序的快速的排序算法。简单插入排序对于大规模乱序数组很慢,因为元素只能一点一点地从数组的一端移动到另一端。例如,如果主键最小的元素正好在数组的尽头,要将它挪到正确的位置就需要n-1次移动。

    希尔排序为了加快速度简单地改进了插入排序,也称为缩小增量排序。

    希尔排序是把待排序数组按一定的数量分组,对每组使用直接插入排序算法排序;然后缩小数量继续分组排序,随着数量逐渐减少,每组包含的元素越来越多,当数量减至 1 时,整个数组恰被分成一组,排序便完成了。这个不断缩小的数量,就构成了一个增量序列,这里的数量称为增量。

    image-20210729135834646

    代码实现

    public class ShellSort {
    
        public static final int[] ARRAY = {12, 9, 6, 11, 5, 1, 14, 2, 10, 4, 8, 7, 13, 3};
    
        public static int[] sort(int[] array) {
            int len = array.length;
            if (len < 2) {
                return array;
            }
            //当前待排序数据,该数据之前的已被排序
            int current;
            //增量
            int gap = len / 2;
            while (gap > 0) {
                for (int i = gap; i < len; i++) {
                    current = array[i];
                    //前面有序序列的索引
                    int index = i - gap;
                    while (index >= 0 && current < array[index]) {
                        array[index + gap] = array[index];
                        //有序序列的下一个
                        index -= gap;
                    }
                    //插入
                    array[index + gap] = current;
                }
                //int相除取整
                gap = gap / 2;
            }
            return array;
        }
    
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    }
    

    时间复杂度

    希尔排序的复杂度和增量序列有关。

    在先前较大的增量下每个子序列的规模都不大,用直接插入排序效率都较高,尽管在随后的增量递减分组中子序列越来越大,由于整个序列的有序性也越来越明显,则排序效率依然较高。

    从理论上说,只要一个数组是递减的,并且最后一个值是1,都可以作为增量序列使用。有没有一个步长序列,使得排序过程中所需的比较和移动次数相对较少,并且无论待排序列记录数有多少,算法的时间复杂度都能渐近最佳呢?但是目前从数学上来说,无法证明某个序列是最好的。

    常用的增量序列:

    • 希尔增量序列 :{n/2, (n / 2)/2, …, 1},其中N为原始数组的长度,这是最常用的序列,但却不是最好的
    • Hibbard序列:{2k-1, …, 3,1}
    • Sedgewick序列:{… , 109 , 41 , 19 , 5,1} 表达式为9 * 4i- 9 * 2i + 1,i = 0,1,2,3,4…

    算法稳定性

    由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,如数组5,2,2,1,第一次排序第一个元素5会和第三个元素2交换,第二个元素2会和第四个元素1交换,原序列中两个2的相对前后顺序就被破坏了,所以希尔排序是一个不稳定的排序算法

    image-20210729165300142

    归并排序

    归并,指合并,合在一起。归并排序(Merge Sort)是建立在归并操作上的一种排序算法。其主要思想是分而治之。什么是分而治之?分而治之就是将一个复杂的计算,按照设定的阈值进行分解成多个计算,然后将各个计算结果进行汇总。即“分”就是把一个大的通过递归成若干个小的,“治”就是将分后的结果在在一起。

    若将两个有序集合并成一个有序表,称为2-路归并,与之对应的还有多路归并。

    image-20210730115340519

    怎么分

    • 对于排序最好的情况来讲,就是只有两个元素,这时候比较大小就很简单,但是还是需要比较
    • 如果拆分为左右各一个,无需比较即是有序的。

    怎么治

    借助一个辅助空数组,把左右两边的数组按照大小比较,按顺序放入辅助数组中即可。

    以下面两个有序数组为例:

    归并排序

    代码实现

    public class MergeSort {
        public static final int[] ARRAY = {8, 5, 6, 4, 3, 1, 7, 2};
    
        public static int[] sort(int[] array) {
            if (array.length < 2) return array;
            int mid = array.length / 2;
            //分成2组
            int[] left = Arrays.copyOfRange(array, 0, mid);
            int[] right = Arrays.copyOfRange(array, mid, array.length);
            //递归拆分
            return merge(sort(left), sort(right));
        }
    
        //治---合并
        public static int[] merge(int[] left, int[] right) {
            int[] result = new int[left.length + right.length];
            //i代表左边数组的索引,j代表右边
            for (int index = 0, i = 0, j = 0; index < result.length; index++) {
                if (i >= left.length) {//说明左侧的数据已经全部取完,取右边的数据
                    result[index] = right[j++];
                } else if (j >= right.length) {//说明右侧的数据已经全部取完,取左边的数据
                    result[index] = left[i++];
                } else if (left[i] > right[j]) {//左边大于右边,取右边的
                    int a = right[j++];
                    result[index] = a;
                } else {//右边大于左边,取左边的
                    result[index] = left[i++];
                }
            }
            return result;
        }
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    }
    

    时间复杂度

    归并排序方法就是把一组n个数的序列,折半分为两个序列,然后再将这两个序列再分,一直分下去,直到分为n个长度为1的序列。然后两两按大小归并。如此反复,直到最后形成包含n个数的一个数组。

    归并排序总时间 = 分解时间 + 子序列排好序时间 + 合并时间
    

    无论每个序列有多少数都是折中分解,所以分解时间是个常数,可以忽略不计,则:

    归并排序总时间 = 子序列排好序时间 + 合并时间
    

    假设处理的数据规模大小为 n,运行时间设为:T(n),则T(n) = n,当 n = 1时,T(1) = 1

    由于在合并时,两个子序列已经排好序,所以在合并的时候只需要 if 判断即可,所以n个数比较,合并的时间复杂度为 n。

    • 将 n 个数的序列,分为两个 n/2 的序列,则:T(n) = 2T(n/2) + n
    • 将 n/2 个数的序列,分为四个 n/4 的序列,则:T(n) = 4T(n/4) + 2n
    • 将 n/4 个数的序列,分为八个 n/8 的序列,则:T(n) = 8T(n/8) + 3n
    • 将 n/2k 个数的序列,分为2k个 n/2k 的序列,则:T(n) = 2kT(n/2k) + kn

    当 T(n/2k) = T(1)时, 即n/2k = 1(此时也是把n分解到只有1个数据的时候),转换为以2为底n的对数:k = log2n,把k带入到T(n)中,得:T(n) = n + nlog2n

    使用大O表示法,去掉常数项 n,省略底数 2,则归并排序的时间复杂度为:O(nlogn)

    算法稳定性

    从原理分析和代码可以看出,为在合并的时候,如果相等,选择前面的元素到辅助数组,所以归并排序是稳定的。

    快速排序

    快速排序是对冒泡排序的一种改进,也是采用分治法的一个典型的应用。JDK中Arrays的sort()方法,具体的排序细节就是使用快速排序实现的。

    从数组中任意选取一个数据(比如数组的第一个数或最后一个数)作为关键数据,我们称为基准数(pivot,或中轴数),然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序,也称为分区(partition)操作。

    问题

    若给定一个无序数组 [8, 5, 6, 4, 3, 1, 7, 2],并指定一个数为基准,拆分数组使得左侧的数都小于等于它 ,右侧的数都大于它。

    基准的选取最优的情况是基准值刚好取在无序区数值的中位数,这样能够最大效率地让两边排序,同时最大地减少递归划分的次数,但是一般很难做到最优。基准的选取一般有三种方式:

    • 选取数组的第一个元素
    • 选取数组的最后一个元素
    • 以及选取第一个、最后一个以及中间的元素的中位数(如4 5 6 7, 第一个4, 最后一个7, 中间的为5, 这三个数的中位数为5, 所以选择5作为基准)。

    思路

    1. 随机选择数组的一个元素,比如 6 为基准,拆分数组同时引入一个初始指针,也叫分区指示器,初始指针指向 -1
    2. 将数组中的元素和基准数遍历比较
    3. 若当前元素大于基准数,不做任何变化
    4. 若当前元素小于等于基准数时,分割指示器右移一位,同时
      • 当前元素下标小于等于分区指示器时,当前元素保持不动
      • 当前元素下标大于分区指示器时,当前元素和分区指示器所指元素交换

    快速排序

    荷兰国旗问题

    荷兰的国旗是由红白蓝三种颜色构成,如图:

    若现在给一个随机的图形,如下:

    image-20210803151023780

    把这些条纹按照颜色排好,红色的在上半部分,白色的在中间部分,蓝色的在下半部分,这类问题称作荷兰国旗问题。

    对应leetcode:颜色分类

    给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
    

    分析:

    假如给定一个数组[8, 3, 6, 2, 5, 1, 7, 5],做如下操作:

    1. 随机选择数组的一个元素,比如 5 为基准,拆分数组同时引入一个左分区指示器,指向 -1,右分区指示器指向基准数(注:此时的基准数为尾元素)

    2. 若当前元素大于基准数,右分区指示器左移一位,当前元素和右分区指示器所指元素交换,

      索引保持不变

    3. 若当前元素小于等于基准数时,左分区指示器右移一位,索引右移

      • 当前元素大于等于左分区指示器所指元素,当前元素保持不动
      • 当前元素小于左分区指示器所指元素,交换

    简单来说就是,左分区指示器向右移动的过程中,如果遇到大于或等于基准数时,则停止移动,右分区指示器向左移动的过程中,如果遇到小于或等于主元的元素则停止移动。这种操作也叫双向快速排序

    345345

    代码实现

    public class QuickSort {
    
        public static final int[] ARRAY = {8, 5, 6, 4, 3, 1, 7, 2};
    
        public static final int[] ARRAY2 = {8, 3, 6, 2, 5, 1, 7, 5};
    
        private static int[] sort(int[] array, int left, int right) {
            if (array.length < 1 || left > right) return null;
            //拆分
            int partitionIndex = partition(array, left, right);
            //递归
            if (partitionIndex > left) {
                sort(array, left, partitionIndex - 1);
            }
            if (partitionIndex < right) {
                sort(array, partitionIndex + 1, right);
            }
            return array;
        }
    
        /**
         * 分区快排操作
         *
         * @param array 原数组
         * @param left  左侧头索引
         * @param right 右侧尾索引
         * @return 分区指示器  最后指向基准数
         */
        public static int partition(int[] array, int left, int right) {
            //基准数下标---随机方式取值,也就是数组的长度随机1-8之间
            int pivot = (int) (left + Math.random() * (right - left + 1));
            //分区指示器索引
            int partitionIndex = left - 1;
            //基准数和尾部元素交换
            swap(array, pivot, right);
            //按照规定,如果当前元素大于基准数不做任何操作;
            //小于基准数,分区指示器右移,且当前元素的索引大于分区指示器,交换
            for (int i = left; i <= right; i++) {
                if (array[i] <= array[right]) {//当前元素小于等于基准数
                    partitionIndex++;
                    if (i > partitionIndex) {//当前元素的索引大于分区指示器
                        //交换
                        swap(array, i, partitionIndex);
                    }
                }
            }
            return partitionIndex;
        }
    
        /**
         * 双向扫描排序
         */
        public static int partitionTwoWay(int[] array, int left, int right) {
            //基准数
            int pivot = array[right];
            //左分区指示器索引
            int leftIndex = left - 1;
            //右分区指示器索引
            int rightIndex = right;
            //索引
            int index = left;
            while (index < rightIndex) {
                //若当前元素大于基准数,右分区指示器左移一位,当前元素和右分区指示器所指元素交换,索引保持不变
                if (array[index] > pivot) {
                    swap(array, index, --rightIndex);
                } else if (array[index] <= pivot) {//当前元素小于等于基准数时,左分割指示器右移一位,索引右移
                    leftIndex++;
                    index++;
                    //当前元素小于等于左分区指示器所指元素,交换
                    if (array[index] < array[leftIndex]) {
                        swap(array, index, leftIndex);
                    }
                }
            }
            //索引和 L 指向同一个元素
            swap(array, right, rightIndex);
            return 1;
        }
    
        //交换
        private static void swap(int[] array, int i, int j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY, 0, ARRAY.length - 1));
            System.out.println("====================双向排序==================");
            print(ARRAY2);
            System.out.println("============================================");
            print(sort(ARRAY2, 0, ARRAY2.length - 1));
        }
    }
    

    时间复杂度

    在拆分数组的时候可能会出现一种极端的情况,每次拆分的时候,基准数左边的元素个数都为0,而右边都为n-1个。这个时候,就需要拆分n次了。而每次拆分整理的时间复杂度为O(n),所以最坏的时间复杂度为O(n2)。什么意思?举个简单例子:

    在不知道初始序列已经有序的情况下进行排序,第1趟排序经过n-1次比较后,将第1个元素仍然定在原来的位置上,并得到一个长度为n-1的子序列;第2趟排序经过n-2次比较后,将第2个元素确定在它原来的位置上,又得到一个长度为n-2的子序列;以此类推,最终总的比较次数:

    C(n) = (n-1) + (n-2) + … + 1 = n(n-1)/2

    所以最坏的情况下,快速排序的时间复杂度为O(n^2)

    而最好的情况就是每次拆分都能够从数组的中间拆分,这样拆分logn次就行了,此时的时间复杂度为O(nlogn)。

    而平均时间复杂度,则是假设每次基准数随机,最后算出来的时间复杂度为O(nlogn)

    参考:快速排序的时间复杂度与空间复杂度

    算法稳定性

    通过上面的分析可以知道,在随机取基准数的时候,数据是可能会发生变化的,所以快速排序有不是稳定的情况。

    堆排序

    这里的堆并不是JVM中堆栈的堆,而是一种特殊的二叉树,通常也叫作二叉堆。它具有以下特点:

    • 它是完全二叉树
    • 堆中某个结点的值总是不大于或不小于其父结点的值

    知识补充

    二叉树

    树中节点的子节点不超过2的有序树

    image-20210804135913978

    满二叉树

    二叉树中除了叶子节点,每个节点的子节点都为2,则此二叉树为满二叉树。

    image-20210804140132004

    完全二叉树

    如果对满二叉树的结点进行编号,约定编号从根结点起,自上而下,自左而右。则深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称之为完全二叉树。

    特点叶子结点只能出现在最下层和次下层,且最下层的叶子结点集中在树的左部。需要注意的是,满二叉树肯定是完全二叉树,而完全二叉树不一定是满二叉树。

    image-20210804144904950

    二叉堆

    二叉堆是一种特殊的堆,可以被看做一棵完全二叉树的数组对象,而根据其性质又可以分为下面两种:

    • 大根堆:每一个根节点都大于等于它的左右孩子节点,也叫最大堆
    • 小根堆:每一个根节点都小于等于它的左右孩子节点,也叫最小堆

    如果把一个数组通过大根堆的方式来表示(数组元素的值是可变的),如下:

    image-20210804180209118

    由此可以推出:

    • 对于位置为 k 的节点,其子节点的位置分别为,左子节点 = 2k + 1右子节点 = 2(k + 1)

      如:对于 k = 1,其节点的对应数组为 5

      左子节点的位置为 3,对应数组的值为 3

      右子节点的位置为 4,对应数组的值为 2

    • 最后一个非叶子节点的位置为 (n/2) - 1,n为数组长度

      如:数组长度为6,则 (6/2) - 1 = 2,即位置 2 为最后一个非叶子节点

    给定一个随机数组[35,63,48,9,86,24,53,11],将该数组视为一个完全二叉树:

    image-20210804190655494

    从上图很明显的可以看出,这个二叉树不符合大根堆的定义,但是可以通过调整,使它变为最大堆。如果从最后一个非叶子节点开始,从下到上,从右往左调整,则:

    image-20210804224254053

    通过上面的调整,该二叉树为最大堆,这个时候开始排序,排序规则:

    • 将堆顶元素和尾元素交换
    • 交换后重新调整元素的位置,使之重新变成二叉堆

    image-20210804234843626

    代码实现

    public class HeapSort {
    
        public static final int[] ARRAY = {35, 63, 48, 9, 86, 24, 53, 11};
    
        public static int[] sort(int[] array) {
            //数组的长度
            int length = array.length;
            if (length < 2) return array;
            //首先构建一个最大堆
            buildMaxHeap(array);
            //调整为最大堆之后,顶元素为最大元素并与微元素交换
            while (length > 0) {//当lenth <= 0时,说明已经到堆顶
                //交换
                swap(array, 0, length - 1);
                length--;//交换之后相当于把树中的最大值弹出去了,所以要--
                //交换之后从上往下调整使之成为最大堆
                adjustHeap(array, 0, length);
            }
            return array;
        }
    
        //对元素组构建为一个对应数组的最大堆
        private static void buildMaxHeap(int[] array) {
            //在之前的分析可知,最大堆的构建是从最后一个非叶子节点开始,从下往上,从右往左调整
            //最后一个非叶子节点的位置为:array.length/2 - 1
            for (int i = array.length / 2 - 1; i >= 0; i--) {
                //调整使之成为最大堆
                adjustHeap(array, i, array.length);
            }
        }
    
        /**
         * 调整
         * @param parent 最后一个非叶子节点
         * @param length 数组的长度
         */
        private static void adjustHeap(int[] array, int parent, int length) {
            //定义最大值的索引
            int maxIndex = parent;
            //parent为对应元素的位置(数组的索引)
            int left = 2 * parent + 1;//左子节点对应元素的位置
            int right = 2 * (parent + 1);//右子节点对应元素的位置
            //判断是否有子节点,再比较父节点和左右子节点的大小
            //因为parent最后一个非叶子节点,所以如果有左右子节点则节点的位置都小于数组的长度
            if (left < length && array[left] > array[maxIndex]) {//左子节点如果比父节点大
                maxIndex = left;
            }
            if (right < length && array[right] > array[maxIndex]) {//右子节点如果比父节点大
                maxIndex = right;
            }
            //maxIndex为父节点,若发生改变则说明不是最大节点,需要交换
            if (maxIndex != parent) {
                swap(array, maxIndex, parent);
                //交换之后递归再次调整比较
                adjustHeap(array, maxIndex, length);
            }
        }
    
        //交换
        private static void swap(int[] array, int i, int j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    }
    

    时间复杂度

    堆的时间复杂度是 O(nlogn)

    参考:堆排序的时间复杂度分析

    算法稳定性

    堆的结构为,对于位置为 k 的节点,其子节点的位置分别为,左子节点 = 2k + 1右子节点 = 2(k + 1),最大堆要求父节点大于等于其2个子节点,最小堆要求父节点小于等于其2个子节点。

    在一个长为n的序列,堆排序的过程是从第n/2开始和其子节点共3个值选择最大(最大堆)或者最小(最大堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1,n/2-2,… 1 这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法。

    参考:排序的稳定性

    思考

    对于快速排序来说,其平均复杂度为O(nlogn),堆排序也是O(nlogn),怎么选择?如下题:

    leetcode:数组中的第K个最大元素

    此题的意思是对于一个无序数组,经过排序后的第 k 个最大的元素。

    我们知道快速排序是需要对整个数组进行排序,这样才能取出第 k 个最大的元素。

    如果使用堆排序,且是最大堆的方式,则第k次循环即可找出第 k 个最大的元素,并不需要吧整个数组排序。

    所以对于怎么选择的问题,要看具体的场景,或者是两者都可。

    计数排序

    一种非比较排序。计数排序对一定范围内的整数排序时候的速度非常快,一般快于其他排序算法。但计数排序局限性比较大,只限于对整数进行排序,而且待排序元素值分布较连续、跨度小的情况。

    如果一个数组里所有元素都是整数,而且都在0-k以内。对于数组里每个元素来说,如果能知道数组里有多少项小于或等于该元素,就能准确地给出该元素在排序后的数组的位置。

    如给定一个0~5范围内的数组[2,5,3,0,2,3,0,3],对于元素5为其中最大的元素,创建一个大小为(5-0+1 = 6)的计数数组,如果原数组中的值对应计数数组的下标,则下标对应计数数组的值加1。

    image-20210806112939098

    问题

    上面是通过数组的最大值来确定计数数组的长度的,但如果需要对学生的成绩进行排序,如学生成绩为:[95,93,92,94,92,93,95,90],如果按照上面的方法来处理,则需要一个大小为100的数组,但是可以看到其中的最小值为90,那也就是说前面 0~89 的位置都没有数据存放,造成了资源浪费。

    如果我们知道了数组的最大值和最小值,则计数数组的大小为(最大值 - 最小值 + 1),如上面数组的最大值为99,最小值为90,则定义计数数组的大小为(95 - 90 + 1 = 6)。并且索引分别对应原数组9095的值。我们把090的范围用一个偏移量来表示,即最小值90就是这个偏移量。

    image-20210806121018728

    代码实现

    public class CountSort {
    
        public static final int[] ARRAY = {2, 5, 3, 0, 2, 3, 0, 3};
        public static final int[] ARRAY2 = {95,93,92,94,92,93,95,90};
    
        //优化前
        private static int[] sort(int[] array) {
            if (array.length < 2) return array;
            //找出数组的最大值
            int max = array[0];
            for (int i : array) {
                if (i > max) {
                    max = i;
                }
            }
            //初始化一个计数数组且值为0
            int[] countArray = new int[max + 1];
            for (int i = 0; i < countArray.length; i++) {
                countArray[i] = 0;
            }
            //填充计数数组
            for (int temp : array) {
                countArray[temp]++;
            }
            int o_index = 0;//原数组下标
            int n_index = 0;//计数数组下标
            while (o_index < array.length) {
                //只要计数数组的下标不为0,就将计数数组的值从新写回原数组
                if (countArray[n_index] != 0) {
                    array[o_index] = n_index;//计数数组下标对应元素组的值
                    countArray[n_index]--;//计数数组的值要-1
                    o_index++;
                } else {
                    n_index++;//上一个索引的值为0后开始下一个
                }
            }
            return array;
        }
    
        //优化后
        private static int[] sort2(int[] array) {
            if (array.length < 2) return array;
            //找出数组中的最大值和最小值
            int min = array[0], max = array[0];
            for (int i : array) {
                if (i > max) {
                    max = i;
                }
                if (i < min) {
                    min = i;
                }
            }
            //定义一个偏移量,即最小值前面0~min的范围,这里直接用一个负数来表示
            int bias = 0 - min;
            //初始化一个计数数组且值为0
            int[] countArray = new int[max - min + 1];
            for (int i = 0; i < countArray.length; i++) {
                countArray[i] = 0;
            }
            for (int temp : array) {
                countArray[temp + bias]++;
            }
            //填充计数数组
            int o_index = 0;//原数组下标
            int n_index = 0;//计数数组下标
            while (o_index < array.length) {
                if (countArray[n_index] != 0) {
                    array[o_index] = n_index - bias;
                    countArray[n_index]--;
                    o_index++;
                } else {
                    n_index++;
                }
            }
            return array;
        }
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
            System.out.println("=================优化排序====================");
            print(ARRAY2);
            System.out.println("============================================");
            print(sort2(ARRAY2));
        }
    }
    

    时间复杂度

    很明显,在排序过程中,我们至少遍历了三次原始数组,一次计数数组,所以它的复杂度为Ο(n+m)。因此,计数排序比任何排序都要块,这是一种牺牲空间换取时间的做法,因为排序过程中需要用一个计数数组来存元素组的出现次数。

    算法稳定性

    在新建的计数数组中记录原始数组中每个元素的数量,如果原始数组有相同的元素,则在输出时,无法保证元素原来的排序,是一种不稳定的排序算法。

    桶排序

    桶排序是计数排序的升级,计数排序可以看成每个桶只存储相同元素,而桶排序每个桶存储一定范围的元素,通过函数的某种映射关系,将待排序数组中的元素映射到各个对应的桶中,对每个桶中的元素进行排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序),最后将非空桶中的元素逐个放入原序列中。

    桶排序需要尽量保证元素分散均匀,否则当所有数据集中在同一个桶中时,桶排序失效。

    image-20210808133137559

    代码实现

    1. 找出数组中的最大值max和最小值min,可以确定出数组所在范围min~max

    2. 根据数据范围确定桶的数量

      • 若桶的数量太少,则桶排序失效
      • 若桶的数量太多,则有的桶可能,没有数据造成空间浪费

      所以桶的数量由我们自己来确定,但尽量让元素平均分布到每一个桶里,这里提供一个方式

      (最大值 - 最小值)/每个桶所能放置多少个不同数值+1

    3. 确定桶的区间,一般是按照(最大值 - 最小值)/桶的数量来划分的,且左闭右开

    public class BucketSort {
    
        public static final int[] ARRAY = {35, 23, 48, 9, 16, 24, 5, 11, 32, 17};
    
        /**
         * @param bucketSize 作为每个桶所能放置多少个不同数值,即数值的类型
         *                   例如当BucketSize==5时,该桶可以存放{1,2,3,4,5}这几种数字,
         *                   但是容量不限,即可以存放100个3
         */
        public static List<Integer> sort(List<Integer> array, int bucketSize) {
            if (array == null || array.size() < 2)
                return array;
            int max = array.get(0), min = array.get(0);
            // 找到最大值最小值
            for (int i = 0; i < array.size(); i++) {
                if (array.get(i) > max)
                    max = array.get(i);
                if (array.get(i) < min)
                    min = array.get(i);
            }
            //获取桶的数量
            int bucketCount = (max - min) / bucketSize + 1;
            //构建桶,初始化
            List<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
            List<Integer> resultArr = new ArrayList<>();
            for (int i = 0; i < bucketCount; i++) {
                bucketArr.add(new ArrayList<>());
            }
            //将原数组的数据分配到桶中
            for (int i = 0; i < array.size(); i++) {
                //区间范围
                bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
            }
    
            for (int i = 0; i < bucketCount; i++) {
                if (bucketSize == 1) {
                    for (int j = 0; j < bucketArr.get(i).size(); j++)
                        resultArr.add(bucketArr.get(i).get(j));
                } else {
                    if (bucketCount == 1)
                        bucketSize--;
                    //对桶中的数据再次用桶进行排序
                    List<Integer> temp = sort(bucketArr.get(i), bucketSize);
                    for (int j = 0; j < temp.size(); j++)
                        resultArr.add(temp.get(j));
                }
            }
            return resultArr;
        }
    
        public static void print(List<Integer> array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(Arrays.stream(ARRAY).boxed().collect(Collectors.toList()));
            System.out.println("============================================");
            print(sort(Arrays.stream(ARRAY).boxed().collect(Collectors.toList()), 2));
        }
    }
    

    时间复杂度

    桶排序算法遍历了2次原始数组,运算量为2N,最后,遍历桶输出排序结果的运算量为N,初始化桶的运算量为M。

    对桶进行排序,不同的排序算法算法复杂度不同,冒泡排序算法复杂度为O(N^2),堆排序、归并排序算法复杂度为O(NlogN),我们以排序算法复杂度为O(NlogN)进行计算,运算量为N/M * log(N/M) * M

    最终的运算量为3N+M+N/M * log(N/M) * M,即3N+M+N(logN-logM),去掉系数,时间复杂度为O(N+M+N(logN-logM))

    参考:桶排序算法详解

    算法稳定性

    桶排序算法在对每个桶进行排序时,若选择稳定的排序算法,则排序后,相同元素的位置不会发生改变,所以桶排序算法是一种稳定的排序算法。

    基数排序

    常见的数据元素一般是由若干位组成的,比如字符串由若干字符组成,整数由若干位0~9数字组成。

    基数排序按照从右往左的顺序,依次将每一位都当做一次关键字,然后按照该关键字对数组排序,同时每一轮排序都基于上轮排序后的结果;当我们将所有的位排序后,整个数组就达到有序状态。基数排序不是基于比较的算法。

    基数是什么意思?对于十进制整数,每一位都只可能是0~9中的某一个,总共10种可能。那10就是它的基,同理二进制数字的基为2;对于字符串,如果它使用的是8位的扩展ASCII字符集,那么它的基就是256。

    基数排序有两种方法:

    • MSD 从高位开始进行排序
    • LSD 从低位开始进行排序

    对于大小范围为0~9的数的组合(若是两位数,就是个位数和十位数的组合),于是可以准备十个桶,然后放到对应的桶里,然后再把桶里的数按照0号桶到9号桶的顺序取出来即可。

    image-20210809173152835

    代码实现

    public class RadixSort {
    
        public static final int[] ARRAY = {82, 50, 21, 5, 66, 48, 43, 79, 14, 37, 25};
    
        public static int[] sort(int[] array) {
            if (array.length < 2) return array;
            //根据最大值算出位数
            int max = array[0];
            for (int temp : array) {
                if (temp > max) {
                    max = temp;
                }
            }
            //算出位数digit
            int maxDigit = 0;
            while (max != 0) {
                max /= 10;
                maxDigit++;
            }
            //创建桶并初始化
            ArrayList<ArrayList<Integer>> bucket = new ArrayList<>();
            for (int i = 0; i < 10; i++) {
                bucket.add(new ArrayList<>());
            }
            //按照从右往左的顺序,依次将每一位都当做一次关键字,然后按照该关键字对数组排序,每一轮排序都基于上轮排序后的结果
            int mold = 10;//取模运算
            int div = 1;//获取对应位数的值
            for (int i = 0; i < maxDigit; i++, mold *= 10, div *= 10) {
                for (int j = 0; j < array.length; j++) {
                    //获取个位/十位/百位......
                    int num = (array[j] % mold) / div;
                    //把数据放入到对应的桶里
                    bucket.get(num).add(array[j]);
                }
                //把桶中的数据重新写回去,并把桶的元素清空,开始第二轮排序
                int index = 0;
                for (int k = 0; k < bucket.size(); k++) {
                    //桶中对应的数据
                    ArrayList<Integer> list = bucket.get(k);
                    for (int m = 0; m < list.size(); m++) {
                        array[index++] = list.get(m);
                    }
                    //清除桶
                    bucket.get(k).clear();
                }
            }
            return array;
        }
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    }
    

    时间复杂度

    计数排序算法的时间复杂度是O(N+M),基数排序算法执行了k次计数排序,所以基数排序算法的时间复杂度为O(K(N+M))。

    算法稳定性

    从上面的分析可以看出,相同元素会按照顺序放进固定的桶内,取出的时候也是按照顺序取出来的,所以基数排序算法是一种稳定的排序算法。

    基数排序 vs 桶排序 vs 计数排序

    这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异

    • 基数排序:根据每一位的关键字来分配桶
    • 桶排序:存储一定范围的值
    • 计数排序:每个桶只存储一个类型值,但是数量不限

    image-20210810001026742

    展开全文
  • 八大排序算法

    万次阅读 多人点赞 2012-07-23 16:45:18
    排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 当n较大,则...

    阅读此文推荐:前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。

    概述

    排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

    我们这里说说八大排序就是内部排序。

        

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

       快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;


     

    1.插入排序—直接插入排序(Straight Insertion Sort)


    基本思想:

    将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序列有序为止。

    要点:设立哨兵,作为临时存储和判断数组边界之用。

    直接插入排序示例:

     

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

    算法的实现:

    void print(int a[], int n ,int i){
    	cout<<i <<":";
    	for(int j= 0; j<8; j++){
    		cout<<a[j] <<" ";
    	}
    	cout<<endl;
    }
    
    
    void InsertSort(int a[], int n)
    {
    	for(int i= 1; i<n; i++){
    		if(a[i] < a[i-1]){               //若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入
    			int j= i-1;	
    			int x = a[i];		 //复制为哨兵,即存储待排序元素
    			a[i] = a[i-1];           //先后移一个元素
    			while(x < a[j]){	 //查找在有序表的插入位置
    				a[j+1] = a[j];
    				j--;		 //元素后移
    			}
    			a[j+1] = x;		 //插入到正确位置
    		}
    		print(a,n,i);			//打印每趟排序的结果
    	}
    	
    }
    
    int main(){
    	int a[8] = {3,1,5,7,2,4,9,6};
    	InsertSort(a,8);
    	print(a,8,8);
    }
    

     

    效率:

     

    时间复杂度:O(n^2).

    其他的插入排序有二分插入排序,2-路插入排序。

     

     2. 插入排序—希尔排序(Shell`s Sort)


    希尔排序是1959 年由D.L.Shell 提出来的,相对直接排序有较大的改进。希尔排序又叫缩小增量排序

    基本思想:

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

    操作方法:

    1. 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
    2. 按增量序列个数k,对序列进行k 趟排序;
    3. 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

    希尔排序的示例:shell排序的排序过程

    假设待排序文件有10个记录,其关键字分别是:49,38,65,97,76,13,27,49,55,04。

    增量系列的取值依次为:5,3,1

     

    算法实现:

    我们简单处理增量序列:增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数

    即:先将要排序的一组记录按某个增量d(n/2,n为要排序数的个数)分成若干组子序列,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。继续不断缩小增量直至为1,最后使用直接插入排序完成排序。

    void print(int a[], int n ,int i){
    	cout<<i <<":";
    	for(int j= 0; j<8; j++){
    		cout<<a[j] <<" ";
    	}
    	cout<<endl;
    }
    /**
     * 直接插入排序的一般形式
     *
     * @param int dk 缩小增量,如果是直接插入排序,dk=1
     *
     */
    
    void ShellInsertSort(int a[], int n, int dk)
    {
    	for(int i= dk; i<n; ++i){
    		if(a[i] < a[i-dk]){			//若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入
    			int j = i-dk;	
    			int x = a[i];			//复制为哨兵,即存储待排序元素
    			a[i] = a[i-dk];			//首先后移一个元素
    			while(x < a[j]){		//查找在有序表的插入位置
    				a[j+dk] = a[j];
    				j -= dk;			 //元素后移
    			}
    			a[j+dk] = x;			//插入到正确位置
    		}
    		print(a, n,i );
    	}
    	
    }
    
    /**
     * 先按增量d(n/2,n为要排序数的个数进行希尔排序
     *
     */
    void shellSort(int a[], int n){
    
    	int dk = n/2;
    	while( dk >= 1  ){
    		ShellInsertSort(a, n, dk);
    		dk = dk/2;
    	}
    }
    int main(){
    	int a[8] = {3,1,5,7,2,4,9,6};
    	//ShellInsertSort(a,8,1); //直接插入排序
    	shellSort(a,8);			  //希尔插入排序
    	print(a,8,8);
    }
    

     

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

     

    3. 选择排序—简单选择排序(Simple Selection Sort)


    基本思想:

    在要排序的一组数中,选出最小(或者最大)的一个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换,依次类推,直到第n-1个元素(倒数第二个数)和第n个元素(最后一个数)比较为止。

    简单选择排序的示例:

     

    操作方法:

    第一趟,从n 个记录中找出关键码最小的记录与第一个记录交换;

    第二趟,从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换;

    以此类推.....

    第i 趟,则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换,

    直到整个序列按关键码有序。

     

    算法实现:

    void print(int a[], int n ,int i){
    	cout<<"第"<<i+1 <<"趟 : ";
    	for(int j= 0; j<8; j++){
    		cout<<a[j] <<"  ";
    	}
    	cout<<endl;
    }
    /**
     * 数组的最小值
     *
     * @return int 数组的键值
     */
    int SelectMinKey(int a[], int n, int i)
    {
    	int k = i;
    	for(int j=i+1 ;j< n; ++j) {
    		if(a[k] > a[j]) k = j;
    	}
    	return k;
    }
    
    /**
     * 选择排序
     *
     */
    void selectSort(int a[], int n){
    	int key, tmp;
    	for(int i = 0; i< n; ++i) {
    		key = SelectMinKey(a, n,i);           //选择最小的元素
    		if(key != i){
    			tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换
    		}
    		print(a,  n , i);
    	}
    }
    int main(){
    	int a[8] = {3,1,5,7,2,4,9,6};
    	cout<<"初始值:";
    	for(int j= 0; j<8; j++){
    		cout<<a[j] <<"  ";
    	}
    	cout<<endl<<endl;
    	selectSort(a, 8);
    	print(a,8,8);
    }
    

     

     简单选择排序的改进——二元选择排序

     

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

    /** 这是伪函数, 逻辑判断不严谨
    void selectSort(int r[],int n) {
    	int i ,j , min ,max, tmp;
    	for (i=1 ;i <= n/2;i++) {  
    		// 做不超过n/2趟选择排序 
    		min = i; max = i ; //分别记录最大和最小关键字记录位置
    		for (j= i+1; j<= n-i; j++) {
    			if (r[j] > r[max]) { 
    				max = j ; continue ; 
    			}  
    			if (r[j]< r[min]) { 
    				min = j ; 
    			}   
    	  }  
    	  //该交换操作还可分情况讨论以提高效率
    	  tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;
    	  tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp; 
     
    	} 
    }
     */
    void selectSort(int a[],int len) {
            int i,j,min,max,tmp;  
            for(i=0; i<len/2; i++){  // 做不超过n/2趟选择排序 
                min = max = i;  
                for(j=i+1; j<=len-1-i; j++){  
    				//分别记录最大和最小关键字记录位置
                    if(a[j] > a[max]){  
                        max = j;  
                        continue;  
                    }  
                    if(a[j] < a[min]){  
                        min = j;  
                    }  
                }  
    			//该交换操作还可分情况讨论以提高效率
                if(min != i){//当第一个为min值,不用交换  
                    tmp=a[min];  a[min]=a[i];  a[i]=tmp;  
                }  
                if(min == len-1-i && max == i)//当第一个为max值,同时最后一个为min值,不再需要下面操作  
                    continue;  
                if(max == i)//当第一个为max值,则交换后min的位置为max值  
                    max = min;  
                if(max != len-1-i){//当最后一个为max值,不用交换  
                    tmp=a[max];  a[max]=a[len-1-i];  a[len-1-i]=tmp;  
                }
    			print(a,len, i);			
            }  
     }

     

    4. 选择排序—堆排序(Heap Sort)


    堆排序是一种树形选择排序,是对直接选择排序的有效改进。

    基本思想:

    堆的定义如下:具有n个元素的序列(k1,k2,...,kn),当且仅当满足

    时称之为堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)。
    若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的。如:

    (a)大顶堆序列:(96, 83,27,38,11,09)

      (b)  小顶堆序列:(12,36,24,85,47,30,53,91)

    初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树(一维数组存储二叉树),调整它们的存储序,使之成为一个堆,将堆顶元素输出,得到n 个元素中最小(或最大)的元素,这时堆的根节点的数最小(或者最大)。然后对前面(n-1)个元素重新调整使之成为堆,输出堆顶元素,得到n 个元素中次小(或次大)的元素。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。称这个过程为堆排序

    因此,实现堆排序需解决两个问题:
    1. 如何将n 个待排序的数建成堆;
    2. 输出堆顶元素后,怎样调整剩余n-1 个元素,使其成为一个新堆。


    首先讨论第二个问题:输出堆顶元素后,对剩余n-1元素重新建成堆的调整过程。
    调整小顶堆的方法:

    1)设有m 个元素的堆,输出堆顶元素后,剩下m-1 个元素。将堆底元素送入堆顶((最后一个元素与堆顶进行交换),堆被破坏,其原因仅是根结点不满足堆的性质。

    2)将根结点与左、右子树中较小元素的进行交换。

    3)若与左子树交换:如果左子树堆被破坏,即左子树的根结点不满足堆的性质,则重复方法 (2).

    4)若与右子树交换,如果右子树堆被破坏,即右子树的根结点不满足堆的性质。则重复方法 (2).

    5)继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成。

    称这个自根结点到叶子结点的调整过程为筛选。如图:


    再讨论对n 个元素初始建堆的过程。
    建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。

    1)n 个结点的完全二叉树,则最后一个结点是第个结点的子树。

    2)筛选从第个结点为根的子树开始,该子树成为堆。

    3)之后向前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点。

    如图建堆初始过程:无序序列:(49,38,65,97,76,13,27,49)


                                 

     算法的实现:

    从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。

    void print(int a[], int n){
    	for(int j= 0; j<n; j++){
    		cout<<a[j] <<"  ";
    	}
    	cout<<endl;
    }
    
    
    
    /**
     * 已知H[s…m]除了H[s] 外均满足堆的定义
     * 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选, 
     *
     * @param H是待调整的堆数组
     * @param s是待调整的数组元素的位置
     * @param length是数组的长度
     *
     */
    void HeapAdjust(int H[],int s, int length)
    {
    	int tmp  = H[s];
    	int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)
        while (child < length) {
    		if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
    			++child ;
    		}
    		if(H[s]<H[child]) {  // 如果较大的子结点大于父结点
    			H[s] = H[child]; // 那么把较大的子结点往上移动,替换它的父结点
    			s = child;		 // 重新设置s ,即待调整的下一个结点的位置
    			child = 2*s+1;
    		}  else {			 // 如果当前待调整结点大于它的左右孩子,则不需要调整,直接退出
    			 break;
    		}
    		H[s] = tmp;			// 当前待调整的结点放到比其大的孩子结点位置上
    	}
    	print(H,length);
    }
    
    
    /**
     * 初始堆进行调整
     * 将H[0..length-1]建成堆
     * 调整完之后第一个元素是序列的最小的元素
     */
    void BuildingHeap(int H[], int length)
    { 
    	//最后一个有孩子的节点的位置 i=  (length -1) / 2
    	for (int i = (length -1) / 2 ; i >= 0; --i)
    		HeapAdjust(H,i,length);
    }
    /**
     * 堆排序算法
     */
    void HeapSort(int H[],int length)
    {
        //初始堆
    	BuildingHeap(H, length);
    	//从最后一个元素开始对序列进行调整
    	for (int i = length - 1; i > 0; --i)
    	{
    		//交换堆顶元素H[0]和堆中最后一个元素
    		int temp = H[i]; H[i] = H[0]; H[0] = temp;
    		//每次交换堆顶元素和堆中最后一个元素之后,都要对堆进行调整
    		HeapAdjust(H,0,i);
      }
    } 
    
    int main(){
    	int H[10] = {3,1,5,7,2,4,9,6,10,8};
    	cout<<"初始值:";
    	print(H,10);
    	HeapSort(H,10);
    	//selectSort(a, 8);
    	cout<<"结果:";
    	print(H,10);
    
    }
    
    

     

    分析:

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

                                   

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

     

    5. 交换排序—冒泡排序(Bubble Sort)


    基本思想:

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

    冒泡排序的示例:

     

    算法的实现:

    void bubbleSort(int a[], int n){
    	for(int i =0 ; i< n-1; ++i) {
    		for(int j = 0; j < n-i-1; ++j) {
    			if(a[j] > a[j+1])
    			{
    				int tmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;
    			}
    		}
    	}
    }

     

    冒泡排序算法的改进

    对冒泡排序常见的改进方法是加入一标志性变量exchange,用于标志某一趟排序过程中是否有数据交换,如果进行某一趟排序时并没有进行数据交换,则说明数据已经按要求排列好,可立即结束排序,避免不必要的比较过程。本文再提供以下两种改进算法:

    1.设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

    改进后算法如下:

    void Bubble_1 ( int r[], int n) {
    	int i= n -1;  //初始时,最后位置保持不变
    	while ( i> 0) { 
    		int pos= 0; //每趟开始时,无记录交换
    		for (int j= 0; j< i; j++)
    			if (r[j]> r[j+1]) {
    				pos= j; //记录交换的位置 
    				int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
    			} 
    		i= pos; //为下一趟排序作准备
    	 } 
    }  
    

     

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

    改进后的算法实现为:

    void Bubble_2 ( int r[], int n){
    	int low = 0; 
    	int high= n -1; //设置变量的初始值
    	int tmp,j;
    	while (low < high) {
    		for (j= low; j< high; ++j) //正向冒泡,找到最大者
    			if (r[j]> r[j+1]) {
    				tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
    			} 
    		--high;					//修改high值, 前移一位
    		for ( j=high; j>low; --j) //反向冒泡,找到最小者
    			if (r[j]<r[j-1]) {
    				tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;
    			}
    		++low;					//修改low值,后移一位
    	} 
    } 

     

    6. 交换排序—快速排序(Quick Sort)


    基本思想:

    1)选择一个基准元素,通常选择第一个元素或者最后一个元素,

    2)通过一趟排序讲待排序的记录分割成独立的两部分,其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。

    3)此时基准元素在其排好序后的正确位置

    4)然后分别对这两部分记录用同样的方法继续进行排序,直到整个序列有序。

    快速排序的示例:

    (a)一趟排序的过程:

    (b)排序的全过程

    算法的实现:

     递归实现:

    void print(int a[], int n){
    	for(int j= 0; j<n; j++){
    		cout<<a[j] <<"  ";
    	}
    	cout<<endl;
    }
    
    void swap(int *a, int *b)
    {
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    int partition(int a[], int low, int high)
    {
    	int privotKey = a[low];								//基准元素
    	while(low < high){								    //从表的两端交替地向中间扫描
    		while(low < high  && a[high] >= privotKey) --high;  //从high 所指位置向前搜索,至多到low+1 位置。将比基准元素小的交换到低端
    		swap(&a[low], &a[high]);
    		while(low < high  && a[low] <= privotKey ) ++low;
    		swap(&a[low], &a[high]);
    	}
    	print(a,10);
    	return low;
    }
    
    
    void quickSort(int a[], int low, int high){
    	if(low < high){
    		int privotLoc = partition(a,  low,  high);  //将表一分为二
    		quickSort(a,  low,  privotLoc -1);			//递归对低子表递归排序
    		quickSort(a,   privotLoc + 1, high);		//递归对高子表递归排序
    	}
    }
    
    int main(){
    	int a[10] = {3,1,5,7,2,4,9,6,10,8};
    	cout<<"初始值:";
    	print(a,10);
    	quickSort(a,0,9);
    	cout<<"结果:";
    	print(a,10);
    
    }

     

    分析:

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


    快速排序的改进

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

    void print(int a[], int n){
    	for(int j= 0; j<n; j++){
    		cout<<a[j] <<"  ";
    	}
    	cout<<endl;
    }
    
    void swap(int *a, int *b)
    {
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    int partition(int a[], int low, int high)
    {
    	int privotKey = a[low];					//基准元素
    	while(low < high){					//从表的两端交替地向中间扫描
    		while(low < high  && a[high] >= privotKey) --high; //从high 所指位置向前搜索,至多到low+1 位置。将比基准元素小的交换到低端
    		swap(&a[low], &a[high]);
    		while(low < high  && a[low] <= privotKey ) ++low;
    		swap(&a[low], &a[high]);
    	}
    	print(a,10);
    	return low;
    }
    
    
    void qsort_improve(int r[ ],int low,int high, int k){
    	if( high -low > k ) { //长度大于k时递归, k为指定的数
    		int pivot = partition(r, low, high); // 调用的Partition算法保持不变
    		qsort_improve(r, low, pivot - 1,k);
    		qsort_improve(r, pivot + 1, high,k);
    	} 
    } 
    void quickSort(int r[], int n, int k){
    	qsort_improve(r,0,n,k);//先调用改进算法Qsort使之基本有序
    
    	//再用插入排序对基本有序序列排序
    	for(int i=1; i<=n;i ++){
    		int tmp = r[i]; 
    		int j=i-1;
    		while(tmp < r[j]){
    			r[j+1]=r[j]; j=j-1; 
    		}
    		r[j+1] = tmp;
    	} 
    
    } 
    
    
    
    int main(){
    	int a[10] = {3,1,5,7,2,4,9,6,10,8};
    	cout<<"初始值:";
    	print(a,10);
    	quickSort(a,9,4);
    	cout<<"结果:";
    	print(a,10);
    
    }

     

    7. 归并排序(Merge Sort)


    基本思想:

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

    归并排序示例:

     

     

    合并方法:

    设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成,两个子表长度分别为n-i +1、n-m。

    1. j=m+1;k=i;i=i; //置两个子表的起始下标及辅助数组的起始下标
    2. 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束
    3. //选取r[i]和r[j]较小的存入辅助数组rf
      如果r[i]<r[j],rf[k]=r[i]; i++; k++; 转⑵
      否则,rf[k]=r[j]; j++; k++; 转⑵
    4. //将尚未处理完的子表中元素存入rf
      如果i<=m,将r[i…m]存入rf[k…n] //前一子表非空
      如果j<=n ,  将r[j…n] 存入rf[k…n] //后一子表非空
    5. 合并结束。
    //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]
    void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
    {
    	int j,k;
    	for(j=m+1,k=i; i<=m && j <=n ; ++k){
    		if(r[j] < r[i]) rf[k] = r[j++];
    		else rf[k] = r[i++];
    	}
    	while(i <= m)  rf[k++] = r[i++];
    	while(j <= n)  rf[k++] = r[j++];
    }

     

    归并的迭代算法

    1 个元素的表总是有序的。所以对n 个元素的待排序列,每个元素可看成1 个有序子表。对子表两两合并生成n/2个子表,所得子表除最后一个子表长度可能为1 外,其余子表长度均为2。再进行两两合并,直到生成n 个元素按关键码有序的表。

    void print(int a[], int n){
    	for(int j= 0; j<n; j++){
    		cout<<a[j] <<"  ";
    	}
    	cout<<endl;
    }
    
    //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]
    void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
    {
    	int j,k;
    	for(j=m+1,k=i; i<=m && j <=n ; ++k){
    		if(r[j] < r[i]) rf[k] = r[j++];
    		else rf[k] = r[i++];
    	}
    	while(i <= m)  rf[k++] = r[i++];
    	while(j <= n)  rf[k++] = r[j++];
    	print(rf,n+1);
    }
    
    void MergeSort(ElemType *r, ElemType *rf, int lenght)
    { 
    	int len = 1;
    	ElemType *q = r ;
    	ElemType *tmp ;
    	while(len < lenght) {
    		int s = len;
    		len = 2 * s ;
    		int i = 0;
    		while(i+ len <lenght){
    			Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并
    			i = i+ len;
    		}
    		if(i + s < lenght){
    			Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并
    		}
    		tmp = q; q = rf; rf = tmp; //交换q,rf,以保证下一趟归并时,仍从q 归并到rf
    	}
    }
    
    
    int main(){
    	int a[10] = {3,1,5,7,2,4,9,6,10,8};
    	int b[10];
    	MergeSort(a, b, 10);
    	print(b,10);
    	cout<<"结果:";
    	print(a,10);
    
    }

     

    两路归并的递归算法

    void MSort(ElemType *r, ElemType *rf,int s, int t)
    { 
    	ElemType *rf2;
    	if(s==t) r[s] = rf[s];
    	else
    	{ 
    		int m=(s+t)/2;			/*平分*p 表*/
    		MSort(r, rf2, s, m);		/*递归地将p[s…m]归并为有序的p2[s…m]*/
    		MSort(r, rf2, m+1, t);		/*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/
    		Merge(rf2, rf, s, m+1,t);	/*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/
    	}
    }
    void MergeSort_recursive(ElemType *r, ElemType *rf, int n)
    {   /*对顺序表*p 作归并排序*/
    	MSort(r, rf,0, n-1);
    }

    8. 桶排序/基数排序(Radix Sort)

    说基数排序之前,我们先说桶排序:

    基本思想:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。
             简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶里面的在进行排序。  

     

     例如要对大小为[1..1000]范围内的n个整数A[1..n]排序  

     首先,可以把桶设为大小为10的范围,具体而言,设集合B[1]存储[1..10]的整数,集合B[2]存储   (10..20]的整数,……集合B[i]存储(   (i-1)*10,   i*10]的整数,i   =   1,2,..100。总共有  100个桶。  

      然后,对A[1..n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。  再对这100个桶中每个桶里的数字排序,这时可用冒泡,选择,乃至快排,一般来说任  何排序法都可以。

      最后,依次输出每个桶里面的数字,且每个桶中的数字从小到大输出,这  样就得到所有数字排好序的一个序列了。  

      假设有n个数字,有m个桶,如果数字是平均分布的,则每个桶里面平均有n/m个数字。如果  

      对每个桶中的数字采用快速排序,那么整个算法的复杂度是  

      O(n   +   m   *   n/m*log(n/m))   =   O(n   +   nlogn   -   nlogm)  

      从上式看出,当m接近n的时候,桶排序复杂度接近O(n)  

      当然,以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的  ,实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中,那就退化成一般的排序了。  

            前面说的几大排序算法 ,大部分时间复杂度都是O(n2),也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O(n)的时间复杂度。但桶排序的缺点是:

            1)首先是空间复杂度比较高,需要的额外开销大。排序有两个数组的空间开销,一个存放待排序数组,一个就是所谓的桶,比如待排序值是从0到m-1,那就需要m个桶,这个桶数组就要至少m个空间。

            2)其次待排序的元素都要在一定的范围内等等。

           桶式排序是一种分配排序。分配排序的特定是不需要进行关键码的比较,但前提是要知道待排序列的一些具体情况。

     

    分配排序的基本思想:说白了就是进行多次的桶式排序。

    基数排序过程无须比较关键字,而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶:O(n)。

    实例:

    扑克牌中52 张牌,可按花色和面值分成两个字段,其大小关系为:
    花色: 梅花< 方块< 红心< 黑心  
    面值: 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A

    若对扑克牌按花色、面值进行升序排序,得到如下序列:


    即两张牌,若花色不同,不论面值怎样,花色低的那张牌小于花色高的,只有在同花色情况下,大小关系才由面值的大小确定。这就是多关键码排序。

    为得到排序结果,我们讨论两种排序方法。
    方法1:先对花色排序,将其分为4 个组,即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序,最后,将4 个组连接起来即可。
    方法2:先按13 个面值给出13 个编号组(2 号,3 号,...,A 号),将牌按面值依次放入对应的编号组,分成13 堆。再按花色给出4 个编号组(梅花、方块、红心、黑心),将2号组中牌取出分别放入对应花色组,再将3 号组中牌取出分别放入对应花色组,……,这样,4 个花色组中均按面值有序,然后,将4 个花色组依次连接起来即可。

    设n 个元素的待排序列包含d 个关键码{k1,k2,…,kd},则称序列对关键码{k1,k2,…,kd}有序是指:对于序列中任两个记录r[i]和r[j](1≤i≤j≤n)都满足下列有序关系:

                                                                  

    其中k1 称为最主位关键码,kd 称为最次位关键码     。

     

    两种多关键码排序方法:

    多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序,分两种方法:

    最高位优先(Most Significant Digit first)法,简称MSD 法

    1)先按k1 排序分组,将序列分成若干子序列,同一组序列的记录中,关键码k1 相等。

    2)再对各组按k2 排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd 对各子组排序后。

    3)再将各组连接起来,便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD 法。

    最低位优先(Least Significant Digit first)法,简称LSD 法

    1) 先从kd 开始排序,再对kd-1进行排序,依次重复,直到按k1排序分组分成最小的子序列后。

    2) 最后将各个子序列连接起来,便可得到一个有序的序列, 扑克牌按花色、面值排序中介绍的方法二即是LSD 法。

     

    基于LSD方法的链式基数排序的基本思想

      “多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字,可以看作由多个数位或多个字符构成的多关键字,此时可以采用“分配-收集”的方法进行排序,这一过程称作基数排序法,其中每个数字或字符可能的取值个数称为基数。比如,扑克牌的花色基数为4,面值基数为13。在整理扑克牌时,既可以先按花色整理,也可以先按面值整理。按花色整理时,先按红、黑、方、花的顺序分成4摞(分配),再按此顺序再叠放在一起(收集),然后按面值的顺序分成13摞(分配),再按此顺序叠放在一起(收集),如此进行二次分配和收集即可将扑克牌排列有序。   

    基数排序:

    是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以是稳定的。

    算法实现:

    Void RadixSort(Node L[],length,maxradix)
    {
       int m,n,k,lsp;
       k=1;m=1;
       int temp[10][length-1];
       Empty(temp); //清空临时空间
       while(k<maxradix) //遍历所有关键字
       {
         for(int i=0;i<length;i++) //分配过程
        {
           if(L[i]<m)
              Temp[0][n]=L[i];
           else
              Lsp=(L[i]/m)%10; //确定关键字
           Temp[lsp][n]=L[i];
           n++;
       }
       CollectElement(L,Temp); //收集
       n=0;
       m=m*10;
      k++;
     }
    }

     

     

     

    总结


    各种排序的稳定性,时间复杂度和空间复杂度总结:

     我们比较时间复杂度函数的情况:

     

                                 时间复杂度函数O(n)的增长情况

    所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。

     

    时间复杂度来说:

    (1)平方阶(O(n2))排序
      各类简单排序:直接插入、直接选择和冒泡排序;
     (2)线性对数阶(O(nlog2n))排序
      快速排序、堆排序和归并排序;
     (3)O(n1+§))排序,§是介于0和1之间的常数。

           希尔排序
    (4)线性阶(O(n))排序
      基数排序,此外还有桶、箱排序。

    说明:

    当原表有序或基本有序时,直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数,时间复杂度可降至O(n);

    而快速排序则相反,当原表基本有序时,将蜕化为冒泡排序,时间复杂度提高为O(n2);

    原表是否有序,对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

     

    稳定性:

    排序算法的稳定性:若待排序的序列中,存在多个具有相同关键字的记录,经过排序, 这些记录的相对次序保持不变,则称该算法是稳定的;若经排序后,记录的相对 次序发生了改变,则称该算法是不稳定的。 
         稳定性的好处:排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,可以避免多余的比较;

    稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序

    不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序

     

    选择排序算法准则:

    每种排序算法都各有优缺点。因此,在实用时需根据不同情况适当选用,甚至可以将多种方法结合起来使用。

    选择排序算法的依据

    影响排序的因素有很多,平均时间复杂度低的算法并不一定就是最优的。相反,有时平均时间复杂度高的算法可能更适合某些特殊情况。同时,选择算法时还得考虑它的可读性,以利于软件的维护。一般而言,需要考虑的因素有以下四点:

    1.待排序的记录数目n的大小;

    2.记录本身数据量的大小,也就是记录中除关键字外的其他信息量的大小;

    3.关键字的结构及其分布情况;

    4.对排序稳定性的要求。

    设待排序元素的个数为n.

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

       快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;
           堆排序 :  如果内存空间允许且要求稳定性的,

           归并排序:它有一定数量的数据移动,所以我们可能过与插入排序组合,先获得一定长度的序列,然后再合并,在效率上将有所提高。

    2)  当n较大,内存空间允许,且要求稳定性 =》归并排序

    3)当n较小,可采用直接插入或直接选择排序。

        直接插入排序:当元素分布有序,直接插入排序将大大减少比较次数和移动记录的次数。

        直接选择排序 :元素分布有序,如果不要求稳定性,选择直接选择排序

    5)一般不使用或不直接使用传统的冒泡排序。

    6)基数排序
    它是一种稳定的排序算法,但有一定的局限性:
      1、关键字可分解。
      2、记录的关键字位数较少,如果密集更好
      3、如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序。

     

    注明:转载请提示出处:http://blog.csdn.net/hguisu/article/details/7776068

     

     

     

    感谢您的支持,我会继续努力的! 扫码打赏,你说多少就多少

             

    展开全文
  • 此文档乃是归并排序算法循环日程赛算法的实现
  • 循环移位与改进插入排序算法
  • 利用了双向循环链表实现了快速排序算法
  • 排序算法之插入排序法

    千次阅读 2017-06-06 21:21:42
    各种排序算法分门别类,其中最常见的是冒泡排序法,选择排序法,插入排序法,快速排序法,shell排序法以及堆排序等等。在此,简单介绍一下插入排序法及其注意事项。

    无论是C语言相关书籍还是算法等等,很多种书籍上都有介绍排序算法,而排序算法重要的在于它的思想,这也是一个程序的灵魂,相信大家也早都知道。在此,我简单介绍一下插入排序法的基本思想,以供一些初学者及掌握不深的学习人员作一个参考。

    其中,插入排序法的核心思想是:

    通过while的循环判断语句,从第二个数字开始,逐个向前一个数字对比,比较大小,若前两个按从小到大顺序排好后,第三个与前两个通过while判断,若大于前一个,则向前插一个位置,也可以理解为与前一个数字交换,交换后再继续与前一个数字比较,直到前一个数字比它小为止,停止比较。通过for语句,跳到下一个数字,继续前插循环比较。

    #include<iostream>
    using namespace std;
    #define N 10
    void InsertSort(int *a, int n)
    {
    	int i, j, temp;
    	for (i = 1; i < n; i++)
    	{
    		temp = a[i];                                        //从第二个数开始,记住后一个数
    		j = i - 1;
    		while ( j >= 0 && temp < a[j])          //与前一个前插比较,若小于前一个数字
    		{                                                           //则将前一个数赋值给后一个数
    			a[j + 1] = a[j];                             //
    			--j;
    		}
    		a[j+1] = temp;                                  //将后一个记住的数赋给前一个数
    	}
    }
    int main()
    {
    	int i;
    	int arr[N];
    	for (i = 0; i < N;i++)
    	{
    			cin >> arr[i];
    		}
    		InsertSort(arr, N);
    		for (i = 0; i < N; i++)
    	{
    			cout << arr[i];
    		}
    		return 0;
    }

    其中,代码部分的while中必须利用temp来作为与前一个数比较的数字,若仍用a[i]来比较,则会出错,因为a[i]经过while比较赋值的过程已不再是原来的数字,这样便会出错。这是初学者容易出错的地方。也是我个人曾经犯过的错误。在此,希望能够给广大学习排序的学习者们给予帮助。



    展开全文
  • 算法学习总结(2)——温故十大经典排序算法

    万次阅读 多人点赞 2019-08-29 14:57:51
    一、什么是排序算法 1.1、排序定义 对一序列对象根据某个关键字进行排序。 1.2、排序术语 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b...

    一、什么是排序算法

    1.1、排序定义

    对一序列对象根据某个关键字进行排序。

    1.2、排序术语

    稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;
    不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;
    内排序:所有排序操作都在内存中完成;
    外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;
    时间复杂度: 一个算法执行所耗费的时间。
    空间复杂度运行完一个程序所需内存的大小。

    1.3、算法总结

    (注意:n指数据规模;k指“桶”的个数;In-place指占用常数内存,不占用额外内存;Out-place指占用额外内存

    1.4、算法分类

    1.5、比较和非比较的区别

    常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序在排序的最终结果里,元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较,才能确定自己的位置。冒泡排序之类的排序中,问题规模为n,又因为需要比较n次,所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中,问题规模通过分治法消减为logN次,所以时间复杂度平均O(nlogn)。比较排序的优势是,适用于各种规模的数据,也不在乎数据的分布,都能进行排序。可以说,比较排序适用于一切需要排序的情况。计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前,应该有多少个元素来排序。针对数组arr,计算arr[i]之前有多少个元素,则唯一确定了arr[i]在排序后数组中的位置。非比较排序只要确定每个元素之前的已有的元素个数即可,所有一次遍历即可解决。算法时间复杂度O(n)非比较排序时间复杂度底,但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

    二、冒泡排序(Bubble Sort)

    冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 

    2.1、算法描述

    • 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
    • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
    • 针对所有的元素重复以上的步骤,除了最后一个;
    • 重复步骤1~3,直到排序完成。

    2.2、动图演示

    2.3、代码实现

    /**
     * 冒泡排序
     *
     * @param array
     * @return
     */
    public static int[] bubbleSort(int[] array) {
    	if (array.length == 0)
    		return array;
    	for (int i = 0; i < array.length; i++)
    		for (int j = 0; j < array.length - 1 - i; j++)
    			if (array[j + 1] < array[j]) {
    				int temp = array[j + 1];
    				array[j + 1] = array[j];
    				array[j] = temp;
    			}
    	return array;
    }

    2.4、算法分析

    最佳情况:T(n) = O(n)   最差情况:T(n) = O(n2)   平均情况:T(n) = O(n2)

    三、选择排序(Selection Sort)

    表现最稳定的排序算法之一,因为无论什么数据进去都是O(n2)的时间复杂度,所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲,选择排序可能也是平时排序一般人想到的最多的排序方法了吧。选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。 

    3.1、算法描述

    n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:

    • 初始状态:无序区为R[1..n],有序区为空;
    • 第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
    • n-1趟结束,数组有序化了。

    3.2、动图演示

    3.3、代码实现

    /**
     * 选择排序
     * @param array
     * @return
     */
    public static int[] selectionSort(int[] array) {
    	if (array.length == 0)
    		return array;
    	for (int i = 0; i < array.length; i++) {
    		int minIndex = i;
    		for (int j = i; j < array.length; j++) {
    			if (array[j] < array[minIndex]) //找到最小的数
    				minIndex = j; //将最小数的索引保存
    		}
    		int temp = array[minIndex];
    		array[minIndex] = array[i];
    		array[i] = temp;
    	}
    	return array;
    }

    3.4、算法分析

    最佳情况:T(n) = O(n2)  最差情况:T(n) = O(n2)  平均情况:T(n) = O(n2)

    四、插入排序(Insertion Sort)

    插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间

    4.1、算法描述

    一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

    • 从第一个元素开始,该元素可以认为已经被排序;
    • 取出下一个元素,在已经排序的元素序列中从后向前扫描;
    • 如果该元素(已排序)大于新元素,将该元素移到下一位置;
    • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
    • 将新元素插入到该位置后;
    • 重复步骤2~5。

    4.2、动图演示

    4.3、代码实现

    /**
     * 插入排序
     * @param array
     * @return
     */
    public static int[] insertionSort(int[] array) {
    	if (array.length == 0)
    		return array;
    	int current;
    	for (int i = 0; i < array.length - 1; i++) {
    		current = array[i + 1];
    		int preIndex = i;
    		while (preIndex >= 0 && current < array[preIndex]) {
    			array[preIndex + 1] = array[preIndex];
    			preIndex--;
    		}
    		array[preIndex + 1] = current;
    	}
    	return array;
    }

    4.4、算法分析

    最佳情况:T(n) = O(n)   最坏情况:T(n) = O(n2)   平均情况:T(n) = O(n2)

    五、希尔排序(Shell Sort)

    希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序希尔排序是把记录按下表的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

    5.1、算法描述

    我们来看下希尔排序的基本步骤,在此我们选择增量gap=length/2,缩小增量继续以gap = gap/2的方式,这种增量选择我们可以用一个序列来表示,{n/2,(n/2)/2...1},称为增量序列。希尔排序的增量序列的选择与证明是个数学难题,我们选择的这个增量序列是比较常用的,也是希尔建议的增量,称为希尔增量,但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,具体算法描述:

    • 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
    • 按增量序列个数k,对序列进行k 趟排序;
    • 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

    5.2、过程演示

    5.3、代码实现

    /**
     * 希尔排序
     *
     * @param array
     * @return
     */
    public static int[] ShellSort(int[] array) {
    	int len = array.length;
    	int temp, gap = len / 2;
    	while (gap > 0) {
    		for (int i = gap; i < len; i++) {
    			temp = array[i];
    			int preIndex = i - gap;
    			while (preIndex >= 0 && array[preIndex] > temp) {
    				array[preIndex + gap] = array[preIndex];
    				preIndex -= gap;
    			}
    			array[preIndex + gap] = temp;
    		}
    		gap /= 2;
    	}
    	return array;
    }

    5.4、算法分析

    最佳情况:T(n) = O(nlog2 n)  最坏情况:T(n) = O(nlog2 n)  平均情况:T(n) =O(nlog2n) 

    六、归并排序(Merge Sort)

    和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(n log n)的时间复杂度。代价是需要额外的内存空间。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。 

    6.1、算法描述

    • 把长度为n的输入序列分成两个长度为n/2的子序列;
    • 对这两个子序列分别采用归并排序;
    • 将两个排序好的子序列合并成一个最终的排序序列。

    6.2、动图演示

    6.3、代码实现

    /**
     * 归并排序
     *
     * @param array
     * @return
     */
    public static int[] MergeSort(int[] array) {
    	if (array.length < 2) return array;
    	int mid = array.length / 2;
    	int[] left = Arrays.copyOfRange(array, 0, mid);
    	int[] right = Arrays.copyOfRange(array, mid, array.length);
    	return merge(MergeSort(left), MergeSort(right));
    }
    /**
     * 归并排序——将两段排序好的数组结合成一个排序数组
     *
     * @param left
     * @param right
     * @return
     */
    public static int[] merge(int[] left, int[] right) {
    	int[] result = new int[left.length + right.length];
    	for (int index = 0, i = 0, j = 0; index < result.length; index++) {
    		if (i >= left.length)
    			result[index] = right[j++];
    		else if (j >= right.length)
    			result[index] = left[i++];
    		else if (left[i] > right[j])
    			result[index] = right[j++];
    		else
    			result[index] = left[i++];
    	}
    	return result;
    }

    6.4、算法分析

    最佳情况:T(n) = O(n)  最差情况:T(n) = O(nlogn)  平均情况:T(n) = O(nlogn)

    七、快速排序(Quick Sort)

    快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

    7.1、算法描述

    快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

    • 从数列中挑出一个元素,称为 “基准”(pivot);
    • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
    • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

    7.2、动图演示

    7.3、代码实现

    /**
     * 快速排序方法
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static int[] QuickSort(int[] array, int start, int end) {
    	if (array.length < 1 || start < 0 || end >= array.length || start > end) return null;
    	int smallIndex = partition(array, start, end);
    	if (smallIndex > start)
    		QuickSort(array, start, smallIndex - 1);
    	if (smallIndex < end)
    		QuickSort(array, smallIndex + 1, end);
    	return array;
    }
    /**
     * 快速排序算法——partition
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static int partition(int[] array, int start, int end) {
    	int pivot = (int) (start + Math.random() * (end - start + 1));
    	int smallIndex = start - 1;
    	swap(array, pivot, end);
    	for (int i = start; i <= end; i++)
    		if (array[i] <= array[end]) {
    			smallIndex++;
    			if (i > smallIndex)
    				swap(array, i, smallIndex);
    		}
    	return smallIndex;
    }
    
    /**
     * 交换数组内两个元素
     * @param array
     * @param i
     * @param j
     */
    public static void swap(int[] array, int i, int j) {
    	int temp = array[i];
    	array[i] = array[j];
    	array[j] = temp;
    }

     


    wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==7.4、算法分析

    最佳情况:T(n) = O(nlogn)   最差情况:T(n) = O(n2)   平均情况:T(n) = O(nlogn) 

    八、堆排序(Heap Sort)

    堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

    8.1、算法描述

    • 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;
    • 将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];
    • 由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

    8.2、动图演示

     

    8.3、代码实现

    //声明全局变量,用于记录数组array的长度;
    static int len;
    /**
     * 堆排序算法
     *
     * @param array
     * @return
     */
    public static int[] HeapSort(int[] array) {
    	len = array.length;
    	if (len < 1) return array;
    	//1.构建一个最大堆
    	buildMaxHeap(array);
    	//2.循环将堆首位(最大值)与末位交换,然后在重新调整最大堆
    	while (len > 0) {
    		swap(array, 0, len - 1);
    		len--;
    		adjustHeap(array, 0);
    	}
    	return array;
    }
    /**
     * 建立最大堆
     *
     * @param array
     */
    public static void buildMaxHeap(int[] array) {
    	//从最后一个非叶子节点开始向上构造最大堆
    	for (int i = (len/2 - 1); i >= 0; i--) { //感谢 @让我发会呆 网友的提醒,此处应该为 i = (len/2 - 1) 
    		adjustHeap(array, i);
    	}
    }
    /**
     * 调整使之成为最大堆
     *
     * @param array
     * @param i
     */
    public static void adjustHeap(int[] array, int i) {
    	int maxIndex = i;
    	//如果有左子树,且左子树大于父节点,则将最大指针指向左子树
    	if (i * 2 < len && array[i * 2] > array[maxIndex])
    		maxIndex = i * 2;
    	//如果有右子树,且右子树大于父节点,则将最大指针指向右子树
    	if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])
    		maxIndex = i * 2 + 1;
    	//如果父节点不是最大值,则将父节点与最大值交换,并且递归调整与父节点交换的位置。
    	if (maxIndex != i) {
    		swap(array, maxIndex, i);
    		adjustHeap(array, maxIndex);
    	}
    }

    8.4、算法分析

    最佳情况:T(n) = O(nlogn) 最差情况:T(n) = O(nlogn) 平均情况:T(n) = O(nlogn)

    九、计数排序(Counting Sort)

    计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

    9.1、算法描述

    • 找出待排序的数组中最大和最小的元素;
    • 统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
    • 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
    • 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。

    9.2、动图演示

    9.3、代码实现

    /**
     * 计数排序
     *
     * @param array
     * @return
     */
    public static int[] CountingSort(int[] array) {
    	if (array.length == 0) return array;
    	int bias, min = array[0], max = array[0];
    	for (int i = 1; i < array.length; i++) {
    		if (array[i] > max)
    			max = array[i];
    		if (array[i] < min)
    			min = array[i];
    	}
    	bias = 0 - min;
    	int[] bucket = new int[max - min + 1];
    	Arrays.fill(bucket, 0);
    	for (int i = 0; i < array.length; i++) {
    		bucket[array[i] + bias]++;
    	}
    	int index = 0, i = 0;
    	while (index < array.length) {
    		if (bucket[i] != 0) {
    			array[index] = i - bias;
    			bucket[i]--;
    			index++;
    		} else
    			i++;
    	}
    	return array;
    }

    9.4、算法分析

    当输入的元素是n 个0到k之间的整数时,它的运行时间是 O(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。最佳情况:T(n) = O(n+k)  最差情况:T(n) = O(n+k)  平均情况:T(n) = O(n+k)

    十、桶排序(Bucket Sort)

    桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排。

    10.1、算法描述

    • 人为设置一个BucketSize,作为每个桶所能放置多少个不同数值(例如当BucketSize==5时,该桶可以存放{1,2,3,4,5}这几种数字,但是容量不限,即可以存放100个3);
    • 遍历输入数据,并且把数据一个一个放到对应的桶里去;
    • 对每个不是空的桶进行排序,可以使用其它排序方法,也可以递归使用桶排序;
    • 从不是空的桶里把排好序的数据拼接起来。 

    注意,如果递归使用桶排序为各个桶排序,则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量,否则会陷入死循环,导致内存溢出。

    10.2、图片演示

    10.3、代码实现

    /**
     * 桶排序
     * 
     * @param array
     * @param bucketSize
     * @return
     */
    public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) {
    	if (array == null || array.size() < 2)
    		return array;
    	int max = array.get(0), min = array.get(0);
    	// 找到最大值最小值
    	for (int i = 0; i < array.size(); i++) {
    		if (array.get(i) > max)
    			max = array.get(i);
    		if (array.get(i) < min)
    			min = array.get(i);
    	}
    	int bucketCount = (max - min) / bucketSize + 1;
    	ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
    	ArrayList<Integer> resultArr = new ArrayList<>();
    	for (int i = 0; i < bucketCount; i++) {
    		bucketArr.add(new ArrayList<Integer>());
    	}
    	for (int i = 0; i < array.size(); i++) {
    		bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
    	}
    	for (int i = 0; i < bucketCount; i++) {
    		if (bucketSize == 1) { // 如果带排序数组中有重复数字时  感谢 @见风任然是风 朋友指出错误
    			for (int j = 0; j < bucketArr.get(i).size(); j++)
    				resultArr.add(bucketArr.get(i).get(j));
    		} else {
    			if (bucketCount == 1)
    				bucketSize--;
    			ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize);
    			for (int j = 0; j < temp.size(); j++)
    				resultArr.add(temp.get(j));
    		}
    	}
    	return resultArr;
    }

    10.4、算法分析

    桶排序最好情况下使用线性时间O(n),桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为O(n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大。 最佳情况:T(n) = O(n+k)   最差情况:T(n) = O(n+k)   平均情况:T(n) = O(n2)  

    十一、基数排序(Radix Sort)

    基数排序也是非比较的排序算法,对每一位进行排序,从最低位开始排序,复杂度为O(kn),为数组长度,k为数组中的数的最大的位数;基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以是稳定的。

    11.1、算法描述

    • 取得数组中的最大数,并取得位数;
    • arr为原始数组,从最低位开始取每个位组成radix数组;
    • 对radix进行计数排序(利用计数排序适用于小范围数的特点);

    11.2、动图演示

    11.3、代码实现

    /**
     * 基数排序
     * @param array
     * @return
     */
    public static int[] RadixSort(int[] array) {
    	if (array == null || array.length < 2)
    		return array;
    	// 1.先算出最大数的位数;
    	int max = array[0];
    	for (int i = 1; i < array.length; i++) {
    		max = Math.max(max, array[i]);
    	}
    	int maxDigit = 0;
    	while (max != 0) {
    		max /= 10;
    		maxDigit++;
    	}
    	int mod = 10, div = 1;
    	ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
    	for (int i = 0; i < 10; i++)
    		bucketList.add(new ArrayList<Integer>());
    	for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
    		for (int j = 0; j < array.length; j++) {
    			int num = (array[j] % mod) / div;
    			bucketList.get(num).add(array[j]);
    		}
    		int index = 0;
    		for (int j = 0; j < bucketList.size(); j++) {
    			for (int k = 0; k < bucketList.get(j).size(); k++)
    				array[index++] = bucketList.get(j).get(k);
    			bucketList.get(j).clear();
    		}
    	}
    	return array;
    }

    11.4、算法分析

    最佳情况:T(n) = O(n * k)   最差情况:T(n) = O(n * k)   平均情况:T(n) = O(n * k)。基数排序有两种方法:MSD 从高位开始进行排序 LSD 从低位开始进行排序 。基数排序 vs 计数排序 vs 桶排序。这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:

    • 基数排序:根据键值的每位数字来分配桶
    • 计数排序:每个桶只存储单一键值
    • 桶排序:每个桶存储一定范围的数值
    展开全文
  • 本文主要讲述python中经常用的三种排序算法,选择排序法,冒泡排序法和插入排序法及其区别。通过对列表里的元素大小排序进行阐述。 原文地址:https://blog.zeruns.tech/index.php/archives/297/ 一、选择排序法 ...
  • 程序员那些必须掌握的排序算法(上)

    万次阅读 多人点赞 2019-08-17 16:03:39
    算法也是一个争论了很久的话题,程序员到底该不该掌握算法?不同的人有不同的答案,而事实上,很多公司都对算法有一定的要求,有些公司直接在面试的时候便会要求面试者手写算法题。这就对程序员的技术要求产生了很大...
  • 八大排序算法(C语言实现)

    万次阅读 多人点赞 2021-05-09 13:50:26
    文章目录插入排序插入排序希尔排序选择排序选择排序排序交换排序冒泡排序快速排序并归排序并归排序 插入排序 插入排序 希尔排序 选择排序 选择排序排序 交换排序 冒泡排序 快速排序 并归排序 并归排序 ...
  • 这个被网友称为最简单的算法(有比sort更简单的么??)当然比起不用自己敲的,这个还是比较简单,让我们直接放代码好吧 2.代码实现 #include<bits/stdc++.h> using namespace std; void gnomesort(int *a,int...
  • 快速排序算法

    万次阅读 多人点赞 2019-01-11 21:09:08
    但是这种算法时间复杂度高,当需要排序的元素较多时,程序运行时间很长,因此产生了快速排序算法。该算法的实现可分为以下几步: 1. 在数组中选一个基准数(通常为数组第一个); 2. 将数组中小于基准数的数据移到...
  • 排序算法

    千次阅读 2021-01-28 19:14:46
    排序算法1 什么是排序以及排序算法的分类1.1 排序的概念1.1 排序的分类2 都有哪些排序算法2.1 插入排序2.1.1 直接插入排序2.1.2 希尔排序2.2 选择排序2.2.1 直接选择排序2.2.2 堆排序2.3 交换排序2.3.1 冒泡排序...
  • 尽管很多语言中都已经提前实现了排序功能,直接提供了排序函数,对于初学者来说,学习各种排序算法的思想仍是十分必要的。   今天主要介绍三种算法:经典的冒泡排序、插入排序和选择排序。不过在此之前,先来看...
  • 常用排序算法之希尔排序法

    千次阅读 2015-06-28 18:30:17
    先将序列按增量划分为元素个数相同的若干组,使用直接插入排序法进行排序,然后不断缩小增量直至为1,最后使用直接插入排序完成排序。 要点:增量的选择以及排序最终以1为增量进行排序结束。 原理: 又称为增量...
  • 大二学过一学期的数据结构,对一些数列排序算法有一些了解...冒泡算法是一个由后向前的排序算法,是一个利用二层嵌套循环完成的排序算法。 其过程可叙述为:1.从数列的第一个数字和第二个数字开始,两两比较相邻数字的
  • 闲来无事回顾复习一下Java排序算法,以前也学过,不过一段时间之后发现对于排序算法记忆不是那么清晰,为加强记忆,特在此做一下笔记,以巩固基础,并与各位朋友分享一下,如有错误请指正,谢谢。冒泡排序法 Bubble ...
  • 排序算法系列:归并排序算法

    万次阅读 多人点赞 2016-05-27 16:32:19
    上一篇我们说了一个非常简单的排序算法——选择排序。其复杂程序完全是冒泡级的,甚至比冒泡还要简单。今天要说的是一个相对比较复杂的排序算法——归并排序。复杂的原因不仅在于归并排序分成了两个部分进行解决问题...
  • 归并排序算法 递归及循环实现

    千次阅读 2016-03-15 22:04:59
    第一步合并相邻长度为1的子数组段,这是因为长度为1的子数组段是已经排好序的。 用一次对数组arr的线性扫描就足以找出所有这些排好序的子数组段。...//递归思想归并排序 //void MergeSort(int a[],int left,int righ
  • 插入排序2.希尔排序 1. 插入排序 步骤: 1.从第一个元素开始,该元素可以认为已经被排序 2.取下一个元素tem,从已排序的元素序列从后往前扫描 3.如果该元素大于tem,则将该元素移到下一位 4.重复步骤3,直到找到已...
  • 冒泡排序算法

    万次阅读 多人点赞 2018-07-19 22:31:43
    什么是冒泡排序呢?...而冒泡排序之所以叫冒泡排序,正是因为这种排序算法的每一个元素都可以向小气泡一样,根据自身大小,一点一点向着数组的一侧移动。具体如何移动呢?我们来看一下例子:  有...
  • 浅谈排序算法:冒泡排序法和选择排序法的区别

    万次阅读 多人点赞 2019-05-22 19:04:27
    之前学习了冒泡排序法和选择排序法,最近被老师问某个道题用的是什么排序法。自己居然答不出来,才发现自己没有真正弄懂,这两个算法的原理和区别,所以····· 1冒泡排序法 1.1什么是冒泡排序法? ...
  • 快速排序算法——C/C++

    万次阅读 多人点赞 2019-06-12 22:55:14
    1、算法思想 快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 2、实现原理 2.1、设置两...
  • 算法对于一个程序员来说可以是一门必修课,基础的排序算法更是重要。在我学习期间,将自己学到的东西进行分享,希望可以帮到大家。 特别感谢《漫画算法-小灰的算法之旅》,魏梦舒著。提供的知识。 一、快速排序的...
  • 打开算法大门,从排序开始
  • PHP冒泡排序算法和快速排序法

    千次阅读 2020-08-30 15:33:22
    PHP冒泡排序算法 算法说明: 冒泡排序大概的意思是依次比较相邻的两个数,然后根据大小做出排序,直至最后两位数。由于在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序。但其实在实际...
  • 排序算法总结

    千次阅读 2019-10-15 15:55:27
    排序算法总结 package com.tulun.src06; /** @author Richard @date 2019/9/23 0023-10:33 *最简单的交换排序,效率极低 冒泡排序法 冒泡排序法2 冒泡排序法的优化:避免有序序列无意义的判断 简单的选择排序法 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 313,696
精华内容 125,478
关键字:

循环排序法