排序 订阅
排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序,若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。 [1] 展开全文
排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序,若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。 [1]
信息
排序算法
快速排序、希尔排序、堆排序等
应用学科
数学 计算机
分    类
稳定排序等
中文名
排序
性    质
计算机内经常进行的一种操作
外文名
sequence
排序概念
将杂乱无章的数据元素,通过一定的方法按关键字顺序排列的过程叫做排序。 [2]  快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法,而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。 [1]  ◆稳定排序:假设在待排序的文件中,存在两个或两个以上的记录具有相同的关键字,在用某种排序法排序后,若这些相同关键字的元素的相对次序仍然不变,则这种排序方法是稳定的。其中冒泡,插入,基数,归并属于稳定排序,选择,快速,希尔,归属于不稳定排序。 [3]  ◆就地排序:若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间为O(1),则称为就地排序。
收起全文
精华内容
下载资源
问答
  • 排序
    万次阅读 多人点赞
    2020-06-17 19:48:33

    八大排序算法

    一、直接插入

    1.基本思路

    在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

    2.代码实现

    • 1.遍历数组,每次循环从第二个数字往前插入
    • 2.设定插入数和得到已经排好序列的最后一个数的位数。temp和j=i-1。
    • 3.从最后一个数开始向前循环,如果插入数小于当前数,就将当前数向后移动一位。
    public static void insertSort(int[] data) {
        int temp;
        for(int i = 1;i < data.length; i++){// 取第i个数,插入前边的有序的序列
            temp = data[i];
            int j;
            for(j = i - 1; j>=0; j--) {// 从第i-1的位置上开始比较
                if(data[j] > temp) {// 若前面的数大,则往后挪一位
                    data[j+1] = data[j];
                } else {
                    break;// 否则,说明要插入的数比较大
                }
            }
            data[j+1] = temp;// 找到这个位置,插入数据
        }
    }
    

    3.时间复杂度和空间复杂度

    直接插入排序的平均复杂度为O(n²),最坏时间复杂度:O(n²),空间复杂度:O(1),没有分配内存。

    二、希尔排序

    针对直接插入排序下的效率问题,有人对此进行了改进与升级,这就是现在的希尔排序。希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

    1.基本思路

    • 1.数的个数为length,i=length/2,将下标差值为i的数分为一组,构成有序序列。

    • 2.再取i=i/2 ,将下标差值为i的数分为一组,构成有序序列。

    • 3.重复第二步,直到k=1执行简单插入排序。

    思路:

    • 1.希尔排序(shell sort)这个排序方法又称为缩小增量排序,是1959年D·L·Shell提出来的。该方法的基本思想是:设待排序元素序列有n个元素,首先取一个整数increment(小于n)作为间隔将全部元素分为increment个子序列,所有距离为increment的元素放在同一个子序列中,在每一个子序列中分别实行直接插入排序。然后缩小间隔increment,重复上述子序列划分和排序工作。直到最后取increment=1,将所有元素放在同一个子序列中排序为止。
    • 2.由于开始时,increment的取值较大,每个子序列中的元素较少,排序速度较快,到排序后期increment取值逐渐变小,子序列中元素个数逐渐增多,但由于前面工作的基础,大多数元素已经基本有序,所以排序速度仍然很快。

    希尔排序举例:
    在这里插入图片描述

    2.代码实现

    • 1.遍历数组,每次循环从第二个数字往前插入
    • 2.设定插入数和得到已经排好序列的最后一个数的位数。temp和j=i-1。
    • 3.从最后一个数开始向前循环,如果插入数小于当前数,就将当前数向后移动一位。

    (1)首先确定每一组序列的下标的间隔,循环每次需要的间隔:int i = length/2; i >0 ; i /= 2

    (2)然后将每一组序列中元素进行插入排序,第二组第一个插入的数字是第一组第一个插入数字之后的那个数组,从i之后每个数字都要进行插入排序,就是插入的序列是各自不同的序列,不是一个一个子序列循环,而是在一个循环中for (int j=i;j<length;j++)完成所有子序列的插入排序。

    (3)直到i=0为止。

    public static void shellSort(int[] array) {
        int length = array.length;
        for (int i = length / 2; i > 0; i /= 2) {//序列的间隔,一直到间隔为一,这时候就只有一个子序列
            for (int j = i; j < length; j++) {//从i之后每个数字都要进行插入排序,就是插入的序列是各自不同的序列
                int temp = array[j];//里面就是直接插入算法
                int k;
                for (k = j - i; k >= 0; k -= i) {//实现各个数字插入排序到不同的序列中,直到间隔为1的时候,只有一个序列,就是完全的一个直接插入排序
                    if (temp < array[k]) {
                        array[k + i] = array[k];
                    } else {
                        break;
                    }
                }
                array[k + i] = temp;//把数字插入到位置上
            }
        }
        System.out.println(Arrays.toString(array));
    }
    

    3.时间复杂度和空间复杂度

    希尔排序的平均时间复杂度为O(n²),空间复杂度O(1) 。

    三、简单选择

    1.基本思路

    基本原理如下:对于给定的一组记录,经过第一轮比较后得到最小的记录,然后将该记录的位置与第一个记录的位置交换;接着对不包括第一个记录以外的其他记录进行第二次比较,得到最小记录并与第二个位置记录交换;重复该过程,直到进行比较的记录只剩下一个为止。

    2.代码实现

    • 1.确定要插入最小值的位置,从0开始到最后int i = 0; i <len ; i++
    • 2.将每次开始位置上的数字暂定为最小值min,从开始数字之后一个个和min比较,再把最小值存放到min
    • 3.将最小值所在位置上的数字和开始位置上的数字交换
    public static void selectSort(int[] array) {
        int len = array.length;
        for (int i = 0; i < len; i++) {//确定每次开始的位置
            int min = array[i];//设定开始数字为最小的值最小值
            int flag = i;
            for (int j = i + 1; j < len; j++) {//把最小值存放到min,从开始数字向后一个个和min比较,再把最小值存放到min
                if (min > array[j]) {
                    min = array[j];
                    flag = j;
                }
            }
            if (flag != i) {
                array[flag] = array[i];
                array[i] = min;
            }
        }
        System.out.println(Arrays.toString(array));
    }
    

    3.时间复杂度和空间复杂度

    简单选择排序的时间复杂度为O(n²)

    四、堆排序

    1.基本思路

    • 1.若array[0,…,n-1]表示一颗完全二叉树的顺序存储模式,则双亲节点指针和孩子结点指针之间的内在关系如下:
    任意一节点指针 i:
    父节点:i==0 ? null : (i-1)/2
    左孩子:2*i + 1
    右孩子:2*i + 2
    
    • 2.堆得定义
    n个关键字序列array[0,...,n-1],当且仅当满足下列要求:(0 <= i <= (n-1)/2)
    ① array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]; 称为小根堆;
    ② array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]; 称为大根堆;
    
    • 3.建立大顶堆

    n个节点的完全二叉树array[0,…,n-1],最后一个节点n-1是第(n-1-1)/2个节点的孩子。对第(n-1-1)/2个节点为根的子树调整,使该子树称为堆。

    对于大根堆,调整方法为:若【根节点的关键字】小于【左右子女中关键字较大者】,则交换。

    之后向前依次对各节点((n-2)/2 - 1)~ 0为根的子树进行调整,看该节点值是否大于其左右子节点的值,若不是,将左右子节点中较大值与之交换,交换后可能会破坏下一级堆,于是继续采用上述方法构建下一级的堆,直到以该节点为根的子树构成堆为止。

    反复利用上述调整堆的方法建堆,直到根节点。

    • 4.堆排序(大顶堆)
    ①将存放在array[0,...,n-1]中的n个元素建成初始堆;
    ②将堆顶元素与堆底元素进行交换,则序列的最大值即已放到正确的位置;
    ③将数组中array[0,...,n-1]前n-1个元素再次形成大根堆,再重复第②③步,直到堆中仅剩下一个元素为止。
    

    2.代码实现

    
    /**
        *  大顶堆排序
        * @param array
        */
    public static void maxHeapSort(int[] array) {
        int i;
        int len = array.length;
        // 构建大顶堆
        for (i = len / 2 - 1; i >= 0; i--) {
            adjustMaxHeap(array, i, len);
        }
        // 堆顶是最大值,交换堆顶和最后一个数,再重新调整最大堆,下一次循环   i--
        for (i = len - 1; i >= 0; i--) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            adjustMaxHeap(array, 0, i);
        }
        System.out.println(Arrays.toString(array));
    }
    
    private static void adjustMaxHeap(int[] a, int pos, int len) {
        int temp;
        int child;
        for (temp = a[pos]; 2 * pos + 1 < len; pos = child) {
            // 数组从0开始,r(i)>=r(2i) r(i)>=r(2i+1)  对应 pos => 2 * pos + 1 和 2 * pos +2
            child = 2 * pos + 1;
            // 有右孩子,且右孩子数值更大
            if (child + 1 < len && a[child] < a[child + 1]) {
                child++;
            }
            // 最大的孩子大于根节点
            if (a[child] > temp) {
                a[pos] = a[child];
            } else {
                break;
            }
        }
        a[pos] = temp;
    }
    

    3.时间复杂度和空间复杂度

    时间复杂度:建堆:o(n),每次调整o(log n),故最好、最坏、平均情况下:o(n*logn);

    五、冒泡排序

    1.基本思路

    一次冒泡将序列中从头到尾所有元素两两比较,将最大的放在最后面。

    将剩余序列中所有元素再次两两比较,将最大的放在最后面。

    重复第二步,直到只剩下一个数。

    2.代码实现

    /**
     * @author fupeng
     * 冒泡排序优化第二版
     * 第一版优化增加flag标记,没有数字交换直接return,最优时间复杂度O(n)
     * 第二版优化,增加tempPosition记录内循环最后一次交换的位置,来缩减内循环的次数
     */
    public static void bubbleSort(int[] array) {
        int len = array.length - 1;
        // 开辟一个临时空间, 存放交换的中间值
        int temp;
        // 记录最后一次交换的位置
        int tempPosition = 0;
        // 要遍历的次数
        for (int i = 0; i < array.length - 1; i++) {
            int flag = 1; // 设置一个标志位
            // 依次比较相邻两个数的大小,遍历一次后,会将前面没有排好序的最大值放到后面位置
            for (int j = 0; j < len; j++) {
                // 比较相邻的元素,如果前面的数大于后面的数,交换
                if (array[j] > array[j + 1]) {
                    temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                    // 发生交换,标志位置0
                    flag = 0;
                    // 记录交换的位置
                    tempPosition = j;
                }
            }
            // 把最后一次交换的位置给len,来缩减内循环的次数
            len = tempPosition;
            // 如果没有交换过元素,则已经有序
            if (flag == 1) {
                System.out.println(Arrays.toString(array));
                return;
            }
        }
        System.out.println(Arrays.toString(array));
    }
    

    3.时间复杂度和空间复杂度

    冒泡排序的最好时间复杂度为O(n),最坏时间复杂度为O(n²),平均时间复杂度为O(n²),空间复杂度为O(1),它是一种稳定的排序算法。

    六、快速排序

    1.基本思路

    快速排序使用分治策略来把一个序列(list)分为两个子序列(sub-lists)。步骤为:

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

    递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

    2.代码实现

    public static void quickSort(int[] array) {
        sort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }
    
    private static void sort(int[] a, int low, int high) {
        int i = low;
        int j = high;
        if (a.length <= 1) {
            return;
        }
        if (i >= j) {
            return;
        }
        int index = a[i];
        while (i < j) {
            while (i < j && a[j] >= index)
                j--;
            if (a[j] < index)
                a[i++] = a[j];
            while (i < j && a[i] <= index)
                i++;
            if (a[i] > index)
                a[j--] = a[i];
        }
        a[i] = index;
        sort(a, low, i - 1);
        sort(a, i + 1, high);
    }
    

    3.时间复杂度和空间复杂度

    虽然 快排的时间复杂度达到了 O(n²),但是在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好。

    七、归并排序

    1.基本思路

    归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

    • 1.分而治之
      在这里插入图片描述

    可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程,递归深度为log2n。

    • 2.合并相邻有序子序列
      再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。

    在这里插入图片描述
    在这里插入图片描述

    2.代码实现

    public static void mergeSort(int[] array) {
        int[] temp = new int[array.length];// 在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
        mergeSort(array, 0, array.length-1, temp);
        System.out.println(Arrays.toString(array));
    }
    
    private static void mergeSort(int[] arr, int left, int right, int []temp) {
        if(left < right) {
            int mid = (left+right) / 2;
            mergeSort(arr, left, mid, temp);// 左边归并排序,使得左子序列有序
            mergeSort(arr, mid+1, right, temp);// 右边归并排序,使得右子序列有序
            merge(arr, left, mid, right, temp);// 将两个有序子数组合并操作
        }
    }
    
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;// 左序列指针
        int j = mid+1;// 右序列指针
        int t = 0;// 临时数组指针
        while (i <= mid && j <= right) {
            if(arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        while(i <= mid) {// 将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while(j <= right) {// 将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        // 将temp中的元素全部拷贝到原数组中
        while(left <= right) {
            arr[left++] = temp[t++];
        }
    }
    

    3.时间复杂度和空间复杂度

    归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法,就是归并排序的优化版本。从上文的图中可看出,每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且,归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。

    八、基数排序

    1.基本思路

    • 1.基数排序的思想就是先排好各位,然后排好各位的基础上排十位,以此类推,直到遍历最高位 次,排序结束(仔细理解最后一句话)
    • 2.基数排序不是比较排序,而是通过分配和收集的过程来实现排序
    • 3.初始化10个桶(固定的),桶下标为0-9
    • 4.通过得到待排序数字的个十百等位的数字,把这个数字对应的item放到对应的桶中
    • 5.基数排序有两种排序方式:LSD和MSD,最小位优先(从右边开始)和最大位优先(从左边开始)

    在这里插入图片描述

    2.代码实现

    public static void radixSort(int[] array) {
        ArrayList<ArrayList<Integer>> queue = new ArrayList<>();
        for (int i = 0; i <10 ; i++) {
            queue.add(new ArrayList<>());// 创建一个基数从0---9 每个数字上都是一个list
        }
        // 找到最大值,并判断最大值是几位数
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
        }
        int time = 0;
        while (max > 0) {
            max /= 10;
            time++;
        }
        for (int i = 0; i < time; i++) {// 循环每一个位数(个位、十位、百位)
            for (int j = 0; j < array.length; j++) {// 循环数组,取每一个值
                int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
                ArrayList<Integer> queue3 = queue.get(x);
    
                queue3.add(array[j]);
                queue.set(x, queue3);
            }
            int count = 0;
            for (int k = 0; k < 10; k++) {
                while (queue.get(k).size() > 0) {
                    ArrayList<Integer> queue4 = queue.get(k);
                    array[count] = queue4.get(0);
                    queue4.remove(0);
                    count++;
                }
            }
        }
    }
    

    3.时间复杂度和空间复杂度

    归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法,就是归并排序的优化版本。从上文的图中可看出,每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且,归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。

    总结

    在这里插入图片描述

    引用:

    https://www.cnblogs.com/mensan/p/10570050.html

    https://www.cnblogs.com/jyroy/p/11248691.html

    https://www.cnblogs.com/chengxiao/p/6194356.html

    https://www.jianshu.com/p/8340dfaea3af

    更多相关内容
  • 插入排序2.希尔排序 1. 插入排序 步骤: 1.从第一个元素开始,该元素可以认为已经被排序 2.取下一个元素tem,从已排序的元素序列从后往前扫描 3.如果该元素大于tem,则将该元素移到下一位 4.重复步骤3,直到找到已...


    1. 插入排序

    步骤:

    1.从第一个元素开始,该元素可以认为已经被排序
    2.取下一个元素tem,从已排序的元素序列从后往前扫描
    3.如果该元素大于tem,则将该元素移到下一位
    4.重复步骤3,直到找到已排序元素中小于等于tem的元素
    5.tem插入到该元素的后面,如果已排序所有元素都大于tem,则将tem插入到下标为0的位置
    6.重复步骤2~5

    动图演示如下:在这里插入图片描述
    思路:
      在待排序的元素中,假设前n-1个元素已有序,现将第n个元素插入到前面已经排好的序列中,使得前n个元素有序。按照此法对所有元素进行插入,直到整个序列有序。
      但我们并不能确定待排元素中究竟哪一部分是有序的,所以我们一开始只能认为第一个元素是有序的,依次将其后面的元素插入到这个有序序列中来,直到整个序列有序为止。
    在这里插入图片描述
    代码如下:

    void InsertSort(int* arr, int n)
    {
    	for (int i = 0; i < n - 1; ++i)
    	{
    		//记录有序序列最后一个元素的下标
    		int end = i;
    		//待插入的元素
    		int tem = arr[end + 1];
    		//单趟排
    		while (end >= 0)
    		{
    			//比插入的数大就向后移
    			if (tem < arr[end])
    			{
    				arr[end + 1] = arr[end];
    				end--;
    			}
    			//比插入的数小,跳出循环
    			else
    			{
    				break;
    			}
    		}
    		//tem放到比插入的数小的数的后面
    		arr[end  + 1] = tem;
    		//代码执行到此位置有两种情况:
    		//1.待插入元素找到应插入位置(break跳出循环到此)
    		//2.待插入元素比当前有序序列中的所有元素都小(while循环结束后到此)
    	}
    }
    

    时间复杂度:最坏情况下为O(N*N),此时待排序列为逆序,或者说接近逆序
          最好情况下为O(N),此时待排序列为升序,或者说接近升序。
    空间复杂度:O(1)

    2.希尔排序

    步骤:
    1.先选定一个小于N的整数gap作为第一增量,然后将所有距离为gap的元素分在同一组,并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量,重复上述操作…
    2.当增量的大小减到1时,就相当于整个序列被分到一组,进行一次直接插入排序,排序完成。
    动图如下:
    在这里插入图片描述
    思路:
    希尔排序,先将待排序列进行预排序,使待排序列接近有序,然后再对该序列进行一次插入排序,此时插入排序的时间复杂度为O(N),

    代码如下:

    //希尔排序
    void ShellSort(int* arr, int n)
    {
    	int gap = n;
    	while (gap>1)
    	{
    		//每次对gap折半操作
    		gap = gap / 2;
    		//单趟排序
    		for (int i = 0; i < n - gap; ++i)
    		{
    			int end = i;
    			int tem = arr[end + gap];
    			while (end >= 0)
    			{
    				if (tem < arr[end])
    				{
    					arr[end + gap] = arr[end];
    					end -= gap;
    				}
    				else
    				{
    					break;
    				}
    			}
    			arr[end + gap] = tem;
    		}
    	}
    }
    

    时间复杂度平均:O(N^1.3)
    空间复杂度:O(1)

    3.选择排序

    思路:
    每次从待排序列中选出一个最小值,然后放在序列的起始位置,直到全部待排数据排完即可。
    实际上,我们可以一趟选出两个值,一个最大值一个最小值,然后将其放在序列开头和末尾,这样可以使选择排序的效率快一倍。

    动图如下:
    在这里插入图片描述
    代码如下:

    //选择排序
    void swap(int* a, int* b)
    {
    	int tem = *a;
    	*a = *b;
    	*b = tem;
    }
    void SelectSort(int* arr, int n)
    {
    	//保存参与单趟排序的第一个数和最后一个数的下标
    	int begin = 0, end = n - 1;
    	while (begin < end)
    	{
    		//保存最大值的下标
    		int maxi = begin;
    		//保存最小值的下标
    		int mini = begin;
    		//找出最大值和最小值的下标
    		for (int i = begin; i <= end; ++i)
    		{
    			if (arr[i] < arr[mini])
    			{
    				mini = i;
    			}
    			if (arr[i] > arr[maxi])
    			{
    				maxi = i;
    			}
    		}
    		//最小值放在序列开头
    		swap(&arr[mini], &arr[begin]);
    		//防止最大的数在begin位置被换走
    		if (begin == maxi)
    		{
    			maxi = mini;
    		}
    		//最大值放在序列结尾
    		swap(&arr[maxi], &arr[end]);
    		++begin;
    		--end;
    	}
    }
    

    时间复杂度:最坏情况:O(N^2)
          最好情况:O(N^2)
    空间复杂度:O(1)

    4.冒泡排序

    思路:
    左边大于右边交换一趟排下来最大的在右边

    动图如下:
    在这里插入图片描述
    代码如下:

    //冒泡排序
    void BubbleSort(int* arr, int n)
    {
    	int end = n;
    	while (end)
    	{
    		int flag = 0;
    		for (int i = 1; i < end; ++i)
    		{
    			if (arr[i - 1] > arr[i])
    			{
    				int tem = arr[i];
    				arr[i] = arr[i - 1];
    				arr[i - 1] = tem;
    				flag = 1;
    			}
    		}
    		if (flag == 0)
    		{
    			break;
    		}
    		--end;
    	}
    }
    

    时间复杂度:最坏情况:O(N^2)
          最好情况:O(N)
    空间复杂度:O(1)

    5.堆排序

    堆排可看之间这篇博文----->[堆排]

    6.快速排序

    5.1 hoare版本(左右指针法)

    思路:
    1、选出一个key,一般是最左边或是最右边的。
    2、定义一个begin和一个end,begin从左向右走,end从右向左走。(需要注意的是:若选择最左边的数据作为key,则需要end先走;若选择最右边的数据作为key,则需要bengin先走)。
    3、在走的过程中,若end遇到小于key的数,则停下,begin开始走,直到begin遇到一个大于key的数时,将begin和right的内容交换,end再次开始走,如此进行下去,直到begin和end最终相遇,此时将相遇点的内容与key交换即可。(选取最左边的值作为key)
    4.此时key的左边都是小于key的数,key的右边都是大于key的数
    5.将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作,此时此部分已有序

    单趟动图如下:
    在这里插入图片描述
    代码如下:

    //快速排序   hoare版本(左右指针法)
    void QuickSort(int* arr, int begin, int end)
    {
    	//只有一个数或区间不存在
    	if (begin >= end)
    		return;
    	int left = begin;
    	int right = end;
    	//选左边为key
    	int keyi = begin;
    	while (begin < end)
    	{
    		//右边选小   等号防止和key值相等    防止顺序begin和end越界
    		while (arr[end] >= arr[keyi] && begin < end)
    		{
    			--end;
    		}
    		//左边选大
    		while (arr[begin] <= arr[keyi] && begin < end)
    		{
    			++begin;
    		}
    		//小的换到右边,大的换到左边
    		swap(&arr[begin], &arr[end]);
    	}
    	swap(&arr[keyi], &arr[end]);
    	keyi = end;
    	//[left,keyi-1]keyi[keyi+1,right]
    	QuickSort(arr, left, keyi - 1);
    	QuickSort(arr,keyi + 1,right);
    }
    

    时间复杂度:
    在这里插入图片描述
    快速排序的过程类似于二叉树其高度为logN,每层约有N个数,如下图所示:在这里插入图片描述

    5.2 挖坑法

    5.2.1 递归

    思路:
    挖坑法思路与hoare版本(左右指针法)思路类似
    1.选出一个数据(一般是最左边或是最右边的)存放在key变量中,在该数据位置形成一个坑
    2、还是定义一个L和一个R,L从左向右走,R从右向左走。(若在最左边挖坑,则需要R先走;若在最右边挖坑,则需要L先走)

    后面的思路与hoare版本(左右指针法)思路类似在此处就不说了

    单趟动图如下:
    在这里插入图片描述
    代码如下:

    //快速排序法  挖坑法
    void QuickSort1(int* arr, int begin, int end)
    {
    	if (begin >= end)
    		return;
    	int left = begin,right = end;
    	int key = arr[begin];
    	while (begin < end)
    	{
    		//找小
    		while (arr[end] >= key && begin < end)
    		{
    			--end;
    		}
    		//小的放到左边的坑里
    		arr[begin] = arr[end];
    		//找大
    		while (arr[begin] <= key && begin < end)
    		{
    			++begin;
    		}
    		//大的放到右边的坑里
    		arr[end] = arr[begin];
    	}
    	arr[begin] = key;
    	int keyi = begin;
    	//[left,keyi-1]keyi[keyi+1,right]
    	QuickSort1(arr, left, keyi - 1);
    	QuickSort1(arr, keyi + 1, right);
    }
    

    5.2.2 非递归

    //单趟排
    int PartSort(int* arr, int begin, int end)
    {
    	int key = arr[begin];
    	while (begin < end)
    	{
    		while (key <= arr[end] && begin < end)
    		{
    			--end;
    		}
    		arr[begin] = arr[end];
    		while (key >= arr[begin] && begin < end)
    		{
    			++begin;
    		}
    		arr[end] = arr[begin];
    	}
    	arr[begin] = key;
    	int meeti = begin;
    	return meeti;
    }
    
    void QuickSortNoR(int* arr, int begin, int end)
    {
    	stack<int> st;
    	//先入右边
    	st.push(end);
    	//再入左边
    	st.push(begin);
    	while (!st.empty())
    	{
    		//左区间
    		int left = st.top();
    		st.pop();
    		//右区间
    		int right = st.top();
    		st.pop();
    		//中间数
    		int mid = PartSort(arr, left, right);
    		//当左区间>=mid-1则证明左区间已经排好序了
    		if (left < mid - 1)
    		{
    			st.push(mid - 1);
    			st.push(left);
    		}
    		//当mid+1>=右区间则证明右区间已经排好序
    		if (right > mid + 1)
    		{
    			st.push(right);
    			st.push(mid + 1);
    		}
    	}
    }
    

    5.3 前后指针法

    思路:
    1、选出一个key,一般是最左边或是最右边的。
    2、起始时,prev指针指向序列开头,cur指针指向prev+1。
    3、若cur指向的内容小于key,则prev先向后移动一位,然后交换prev和cur指针指向的内容,然后cur指针++;若cur指向的内容大于key,则cur指针直接++。如此进行下去,直到cur到达end位置,此时将key和++prev指针指向的内容交换即可。

    经过一次单趟排序,最终也能使得key左边的数据全部都小于key,key右边的数据全部都大于key。

    然后也还是将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作

    //快速排序法  前后指针版本
    void QuickSort2(int* arr, int begin, int end)
    {
    	if (begin >= end)
    		return;
    	int cur = begin, prev = begin - 1;
    	int keyi = end;
    	while (cur != keyi)
    	{
    		if (arr[cur] < arr[keyi] && ++prev != cur)
    		{
    			swap(&arr[cur], &arr[prev]);
    		}
    		++cur;
    	}
    	swap(&arr[++prev],&arr[keyi]);
    	keyi = prev;
    	//[begin,keyi -1]keyi[keyi+1,end]
    	QuickSort2(arr, begin, keyi - 1);
    	QuickSort2(arr, keyi + 1, end);
    
    }
    
    展开全文
  • 经典十大排序算法【Java版完整代码】写在前面的话十大排序算法对比冒泡排序快速排序直接选择排序排序归并排序插入排序希尔排序计数排序排序基数排序 写在前面的话        ...

    写在前面的话

           虽然已经有很多人总结过这十大排序算法,优秀的文章也不少,但是Java完整版的好像不多,还存在某些文章代码存在错误的情况,同时也为了自己练手,决定把所有的写一遍巩固下,同时也真诚的希望阅读到这篇文章的小伙伴们可以自己去从头敲一遍,不要粘贴复制!希望我的文章对你有所帮助,每天进步一点点!!!

           我用通俗的理解写下对算法的解释,对某个算法的运行过程不是很理解的话或者想看比较官方的解释的话,单独搜索某个算法,看几篇不同的解释,就可以有自己的理解了,这里我主要展示代码以及进行通俗的解释!整起来,再强调一次,一定要自己敲一遍,这样才能理解的更深刻!

    十大排序算法对比

    在这里插入图片描述

    关于最后一列的稳定性,我稍微解释下,例如对序列:1 2 4 2 6 排序,序列中存在两个2,如果我们把这两个2标记上(让他俩不同),排序之后,前面的2还在前面,那么就称这种排序是稳定的,反之不稳定。

    冒泡排序

    简单解释:
           原理就如算法名字一样,就像水中的气泡一样,每次我都把最大的或最小的放到最后面,这样总共需要n-1趟即可完成排序,这就是第一层循环,第二次循环就是遍历未被固定的那些数(理解成数组左边的数,因为每层循环都会把最大或最小的数升到最右边固定起来,下次就不遍历这些数了),两层循环遍历结束后,所有的数就排好序了。
           两层循环所以冒泡排序算法的时间复杂度是O( n 2 n^{2} n2),是一个非常高的时间复杂度,我在下面的代码进行了优化,加了一个标志位,如果上一次循环未发生交换,就说明已经是有序的了,就不继续下去了,反之继续进行下一轮。

    本文的图片来源网络,仅用于大家学习,侵权联系删除!(下同)

    完整代码:

    package com.keafmd.Sequence;
    
    /**
     * Keafmd
     *
     * @ClassName: BubbleSort
     * @Description: 冒泡排序
     * @author: 牛哄哄的柯南
     * @date: 2021-06-24 10:31
     */
    public class BubbleSort {
    
        //冒泡排序
        public static void bubbleSort(int[] arr, boolean ascending) { //exchange标志表示为升序排序还是降序排序
    
            boolean flag = true; //加一个标志位,记录上一次是否发生了交换,如果是,我们则进行下一轮,如果没有,说明已经冒泡好了
    
            for (int i = 1; i < arr.length && flag; i++) { //控制次数,第几趟排序,只需要n-1趟,有交换时进行,只有flag=false就说明上一次一个元素都没有进行交换
    
                /*System.out.print("第"+i+"次遍历:");
                for (int i1 : arr) {
                    System.out.print(i1+" ");
                }
                System.out.println();*/
    
                flag = false; //假定未交换
    
                for (int j = 0; j < arr.length - i; j++) {
    
                    if (ascending ? arr[j] > arr[j + 1] : arr[j] < arr[j + 1]) { //控制升序还是降序
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                        flag = true;
                    }
    
                }
            }
        }
    
        //冒泡排序 -- 默认不传参升序
        public static void bubbleSort(int[] arr) {
            bubbleSort(arr, true);
        }
    }
    

    测试代码:

    升序排序(从小到大)

    package com.keafmd.Sequence;
    
    import java.util.*;
    import java.util.stream.IntStream;
    import java.util.stream.Stream;
    
    /**
     * Keafmd
     *
     * @ClassName: Sort
     * @Description: 十大排序算法
     * @author: 牛哄哄的柯南
     * @date: 2021-06-16 21:27
     */
    public class Sort {
        public static void main(String[] args) {
    
            int[] nums = {12, 4, 25, 47, 58, 34, 25, 9, 99, 26, 1, -13, 162, 10093, -66, -1};
            int[] temparr;
    
            //测试冒泡排序
            System.out.println("测试冒泡排序:");
            temparr = nums.clone();
            BubbleSort.bubbleSort(temparr);
            //逆序排序
            //BubbleSort.bubbleSort(temparr,false);
            for (int i = 0; i < temparr.length; i++) {
                System.out.print(temparr[i] + " ");
            }
            System.out.println();
    
        }
    }
    

    运行结果:

    测试冒泡排序:
    -66 -13 -1 1 4 9 12 25 25 26 34 47 58 99 162 10093 
    

    降序排序(从大到小)

    //测试冒泡排序
    System.out.println("测试冒泡排序:");
    temparr = nums.clone();
    BubbleSort.bubbleSort(temparr,false);
    for (int i = 0; i < temparr.length; i++) {
        System.out.print(temparr[i] + " ");
    }
    System.out.println();
    

    运行结果:

    测试冒泡排序:
    10093 162 99 58 47 34 26 25 25 12 9 4 1 -1 -13 -66 
    

    下面几个算法的测试也就是换了下类名和方法名(换成相应的排序算法),如果想降序就在数组后面传个false即可。我就不一一复制了,我在最下面给出含所有算法的测试类,需要的自取即可。

    快速排序

    简单解释:
    快速排序就是每次找一个基点(第一个元素),然后两个哨兵,一个从最前面往后走,一个从最后面往前面走,如果后面那个哨兵找到了一个比基点大的数停下来,前面那个哨兵找到比基点大的数停下来,然后交换两个哨兵找到的数,如果找不到最后两个哨兵就会碰到一起就结束,最后交换基点和哨兵相遇的地方的元素,然后就将一个序列分为比基点小的一部分和比基点大的一部分,然后递归左半部分和右半部分,最后的结果就是有序的了。

    完整代码:

    package com.keafmd.Sequence;
    
    /**
     * Keafmd
     *
     * @ClassName: QuickSort
     * @Description: 快速排序
     * @author: 牛哄哄的柯南
     * @date: 2021-06-24 10:32
     */
    public class QuickSort {
    
        //快速排序
        public static void quickSort(int[] arr) {
            quickSort(arr, true);
        }
    
        public static void quickSort(int[] arr, boolean ascending) {
            if (ascending) {
                quickSort(arr, 0, arr.length - 1, true);
            } else {
                quickSort(arr, 0, arr.length - 1, false);
            }
        }
    
        public static void quickSort(int[] arr, int begin, int end, boolean ascending) {
            if (ascending)
                quickSort(arr, begin, end);
            else
                quickSortDescending(arr, begin, end);
        }
    
        //快排序升序 -- 默认
        public static void quickSort(int[] arr, int begin, int end) {
            if (begin > end) { //结束条件
                return;
            }
            int base = arr[begin];
            int i = begin, j = end;
            while (i < j) { // 两个哨兵(i左边,j右边)没有相遇
                while (arr[j] >= base && i < j) { //哨兵j没找到比base小的
                    j--;
                }
                while (arr[i] <= base && i < j) { //哨兵i没找到比base大的
                    i++;
                }
                if (i < j) { //如果满足条件则交换
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
    
            }
            //最后将基准为与i和j相等位置的数字交换
            arr[begin] = arr[i];
            arr[i] = base;
            quickSort(arr, begin, i - 1); //递归调用左半数组
            quickSort(arr, i + 1, end); //递归调用右半数组
    
        }
    
        //快排序降序
        public static void quickSortDescending(int[] arr, int begin, int end) {
            if (begin > end) { //结束条件
                return;
            }
            int base = arr[begin];
            int i = begin, j = end;
            while (i < j) { // 两个哨兵(i左边,j右边)没有相遇
                while (arr[j] <= base && i < j) { //哨兵j没找到比base大的
                    j--;
                }
                while (arr[i] >= base && i < j) { //哨兵i没找到比base小的
                    i++;
                }
                if (i < j) { //如果满足条件则交换
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
    
            }
            //最后将基准为与i和j相等位置的数字交换
            arr[begin] = arr[i];
            arr[i] = base;
            quickSortDescending(arr, begin, i - 1); //递归调用左半数组
            quickSortDescending(arr, i + 1, end); //递归调用右半数组
    
        }
    
    }
    

    直接选择排序

    简单解释:
    数组分为已排序部分(前面)和待排序序列(后面)
    第一次肯定所有的数都是待排序的
    从待排序的序列中找到最大或最小的那个元素,放到前面的已排序部分,然后一直找,不断缩小待排序的范围,直到所有的数都是已排序的了

    完整代码:

    package com.keafmd.Sequence;
    
    /**
     * Keafmd
     *
     * @ClassName: SelectSort
     * @Description: 选择排序
     * @author: 牛哄哄的柯南
     * @date: 2021-06-24 10:33
     */
    public class SelectSort {
    
        //直接选择排序
        public static void selectSort(int[] arr, boolean ascending) {
            for (int i = 0; i < arr.length; i++) {
                int m = i; //最小值或最小值的下标
                for (int j = i + 1; j < arr.length; j++) {
                    if (ascending ? arr[j] < arr[m] : arr[j] > arr[m]) {
                        m = j; //找到待排序的数中最小或最大的那个数,记录下标
                    }
    
                }
                //交换位置
                int temp = arr[i];
                arr[i] = arr[m];
                arr[m] = temp;
    
            }
        }
    
        public static void selectSort(int[] arr) {
            selectSort(arr, true);
        }
    }
    

    堆排序

    先理解下大顶堆和小顶堆,看图
    大顶堆,双亲结点的值比每一个孩子结点的值都要大。根结点值最大
    小顶堆,双亲结点的值比每一个孩子结点的值都要小。根结点值最小

    简单解释:
    构建好大顶堆或小顶堆结构,这样最上面的就是最大值或最小值,那么我们取出堆顶元素,然后重新构建结构,一直取,一直重新构建,那么最后达到排序的效果了。

    完整代码:

    package com.keafmd.Sequence;
    
    /**
     * Keafmd
     *
     * @ClassName: HeapSort
     * @Description: 堆排序
     * @author: 牛哄哄的柯南
     * @date: 2021-06-24 10:34
     */
    public class HeapSort {
    
        //堆排序
        public static void heapSort(int[] arr) {
            //对传入的数组进行建立堆,这里默认建立大顶堆,进行升序排列
            heapSort(arr, true);
        }
    
        public static void heapSort(int[] arr, boolean maxheap) {
    
            //1.构建大顶堆
            for (int i = arr.length / 2 - 1; i >= 0; i--) {
                //从第一个非叶子结点从下至上,从右至左调整结构
                sift(arr, i, arr.length , maxheap);
            }
    
            //2.调整堆结构+交换堆顶元素与末尾元素
            for (int j = arr.length - 1; j > 0; j--) {
    
                //现在的数组第一个就是根结点,最小值所在,进行交换,把它放到最右边
                int temp = arr[j];
                arr[j] = arr[0];
                arr[0] = temp;
    
                //重新建立堆
                sift(arr, 0, j , maxheap); //重新对堆进行调整
            }
        }
    
        //建立堆的方法
        /**
         * 私有方法,只允许被堆排序调用
         *
         * @param arr     要排序数组
         * @param parent  当前的双亲节点
         * @param len     数组长度
         * @param maxheap 是否建立大顶堆
         */
        private static void sift(int[] arr, int parent, int len, boolean maxheap) {
    
            int value = arr[parent]; //先取出当前元素i
    
            for (int child = 2 * parent + 1; child < len; child = child * 2 + 1) { //从parent结点的左子结点开始,也就是2*parent+1处开始
    
                if (child+1 < len && (maxheap ? arr[child] < arr[child + 1] : arr[child] > arr[child + 1])) { //如果左子结点小于右子结点,child指向右子结点
                    child++; //右孩子如果比左孩子大,我们就将现在的孩子换到右孩子
                }
    
                //判断是否符合大顶堆的特性, 如果右孩子大于双亲,自然左孩子也大于双亲,符合
                //如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
                if (maxheap ? value < arr[child] : value > arr[child]) {
                    arr[parent]=arr[child];
                    parent = child;
                }
                else {//如果不是,说明已经符合我们的要求了。
                    break;
                }
            }
            arr[parent] =value; //将value值放到最终的位置
    
    
        }
    
    }
    

    归并排序

    简单解释:
    该算法是采用分治法,把数组不断分割,直至成为单个元素,然后比较再合并(合并的过程就是两部分分别从头开始比较,取出最小或最大元素的放到新的区域内,继续取两部分中最大或最小的元素,直到这两部分合并完,最后所有的都合并完,最后形成完整的有序序列)

    完整代码:

    package com.keafmd.Sequence;
    
    /**
     * Keafmd
     *
     * @ClassName: MergeSort
     * @Description: 归并排序
     * @author: 牛哄哄的柯南
     * @date: 2021-06-24 10:35
     */
    public class MergeSort {
    
        //归并排序
        public static void mergeSort(int []arr ,boolean ascending){
            int[] temp = new int[arr.length]; //在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
            mergeSort(arr,0,arr.length-1,temp,ascending);
        }
        public static void mergeSort(int []arr){
            mergeSort(arr,true);
        }
    
        /**
         *
         * @param arr 传入的数组
         * @param left 当前子数组的起始下标
         * @param right 当前子数组的结束下标
         * @param temp 拷贝暂存数组
         */
        public static void mergeSort(int []arr,int left,int right,int[] temp,boolean ascending){
            if(left<right){ //这里是递归结束的条件,我们是对半分,那当left==right的时候肯定大家都是只有一个元素了。
    
                //对半分,比如总长度是10,left=0,right=9,mid=4确实是中间分了,0~4,5~9
                //当长度9,left=0,right=8,mid=4,0~4,5~8
                int mid = left + (right-left)/2; // 防止越界的写法
                //int mid = (left+right)/2;
    
                mergeSort(arr,left,mid,temp,ascending); //左边归并排序,使得左子序列有序
                mergeSort(arr,mid+1,right,temp,ascending); //右边归并排序,使得右子序列有序
    
                merge(arr,left,mid,right,temp,ascending); //将两个有序子数组合并操作
            }
        }
    
        private static void merge(int[] arr,int left,int mid,int right,int[] temp,boolean ascending){
            int i = left; //左序列起始下标
            int j = mid+1; //右序列起始下标
            int t = 0; //临时数组指针
            while(i<=mid&&j<=right){
                if(ascending?arr[i]<arr[j]:arr[i]>arr[j]){ //比较两个序列第一个元素谁小,谁小先拷贝谁到temp,然后对应子序列下标加1
                    temp[t++] = arr[i++];
                }else {
                    temp[t++] = arr[j++];
                }
            }
    
            while(i<=mid){ //将左边剩余元素填充进temp中——左序列有一些数总是比右边的大的数
                temp[t++] = arr[i++];
            }
    
            while(j<=right){ //将右序列剩余元素填充进temp中——右序列有一些数总是比左边的大的数
                temp[t++] = arr[j++];
            }
    
            t = 0;
    
            //将temp中的元素全部拷贝到原数组中
            while(left<=right){
                arr[left++] = temp[t++];
            }
    
        }
    
    }
    

    插入排序

    简单解释:
    最简单的理解就是打地主时我们拿到牌后的整理过程,从第二个牌(假设我们拿起来这个牌开始比较)开始,(说下升序)从后往前比较如果比前面的那个牌小,就把牌往后移动,直到找到一个合适的位置(这个位置的前面的那个牌不比这个要放下的牌大)就把这个牌放到这个位置,慢慢的前面的部分变得有序,直至全部有序即可。

    完整代码:

    package com.keafmd.Sequence;
    
    /**
     * Keafmd
     *
     * @ClassName: StraghtInsertSort
     * @Description: 插入排序
     * @author: 牛哄哄的柯南
     * @date: 2021-06-24 10:36
     */
    public class StraghtInsertSort {
        //插入排序
        public static void straghtInsertSort(int[] arr) {
            straghtInsertSort(arr, true);//默认进行升序
        }
    
        public static void straghtInsertSort(int[] arr, boolean ascending) {
    
            for (int i = 1; i < arr.length; i++) {
                int temp = arr[i];
                int j=0; //这就是那个合适的位置
                for (j = i - 1; j >= 0 && (ascending ? temp < arr[j] : temp > arr[j]); j--) {
                    arr[j + 1] = arr[j];
                }
                //把牌放下,为啥是j+1,
                //是因为上面的循环遍历到不符合情况的时候 j是合适的位置的前面的那个数的位置
                //有点拗口,但是就是这个意思,看图方便理解下
                arr[j + 1] = temp;
    
    
            }
    
        }
    }
    

    希尔排序

    简单解释:
    希尔排序是插入排序的改进版,我们理解一个叫做下标差的的东西,也就是下面那个图中的增量d,初始下标差为arr.length/2,然后继续/2,对在同一下标差(相当于把这几个数单独拿出来了)的若干个数进行插入排序即可。



    完整代码:

    package com.keafmd.Sequence;
    
    /**
     * Keafmd
     *
     * @ClassName: ShellSort
     * @Description: 希尔排序
     * @author: 牛哄哄的柯南
     * @date: 2021-06-24 10:39
     */
    public class ShellSort {
    
        public static void shellSort(int[] arr) {
            shellSort(arr,true);
        }
    
        public static void shellSort(int[] arr,boolean ascending) {
    
            for(int d = arr.length/2;d>0;d/=2){
    
                for(int i=d;i< arr.length;i++){
                    int temp = arr[i];
                    int j=0;
                    for(j=i-d;j>=0&&(ascending?temp<arr[j]:temp>arr[j]);j-=d){
                        arr[j+d]=arr[j];
                    }
                    arr[j+d] = temp;
                }
            }
    
        }
    }
    

    计数排序

    简单解释:
    这个排序算法看名字也很好理解,就是就是额外找个数组来计数,然后在这个数组从小到大或从大到小把数取出来即可。

    完整代码:

    package com.keafmd.Sequence;
    
    /**
     * Keafmd
     *
     * @ClassName: CountSort
     * @Description: 计数排序
     * @author: 牛哄哄的柯南
     * @date: 2021-06-24 11:31
     */
    public class CountSort {
    
        public static void countSort(int[]arr){
            countSort(arr,true);
        }
    
        public static void countSort(int[]arr,boolean ascending){
            int d,min=arr[0],max=arr[0];
    
            //找出最大、最小值
            for(int i=0;i< arr.length;i++){
                if(arr[i]<min){
                    min =arr[i];
                }
                if(arr[i]>max){
                    max = arr[i];
                }
            }
    
            //建立一个用于计数的数组
            d = min;
            int[] count_map = new int[max-min+1];
            for(int i=0;i< arr.length;i++){
                count_map[arr[i]-d]++;
            }
    
            int k =0;
            if(ascending){
                for(int i=0;i< arr.length;){
                    if(count_map[k]>0){
                        arr[i] = k+d;
                        i++;
                        count_map[k]--;
                    }else
                        k++;
                }
            }else {
                for(int i=arr.length-1;i>=0;){
                    if(count_map[k]>0){
                        arr[i] = k+d;
                        i--;
                        count_map[k]--;
                    }else
                        k++;
                }
            }
    
        }
    }
    

    桶排序

    简单解释:
    就是把一个数组分成几个桶(其实是几个区间,从小到大或从大到小的几个区间)装,然后让每个桶(区间)有序,然后取出来放一起就可以了,相当于把几个有序的段拿出来放一起,自然还是有序的,当然需要是按照区间的顺序拿了。

    完整代码:

    package com.keafmd.Sequence;
    
    import java.util.ArrayList;
    import java.util.Collections;
    
    /**
     * Keafmd
     *
     * @ClassName: BucketSort
     * @Description: 桶排序
     * @author: 牛哄哄的柯南
     * @date: 2021-06-24 13:32
     */
    public class BucketSort {
    
        public static void bucketSort(int[] arr){
            bucketSort(arr,true);
        }
    
        public static void bucketSort(int[] arr,boolean ascending){
            if(arr==null||arr.length==0){
                return;
            }
            //计算最大值与最小值
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            for(int i=0;i<arr.length;i++){
                max = Math.max(arr[i],max);
                min = Math.min(arr[i],min);
            }
    
            //计算桶的数量
            int bucketNUm = (max-min)/ arr.length+1;
            ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNUm);
            for(int i=0;i<bucketNUm;i++){
                bucketArr.add(new ArrayList<>());
            }
    
            //将每个元素放入桶中
            for(int i=0;i<arr.length;i++){
                int num = (arr[i]-min)/ (arr.length);
                bucketArr.get(num).add(arr[i]);
            }
    
            //对每个桶进行排序
            for (int i = 0; i < bucketArr.size(); i++) {
                //用系统的排序,速度肯定没话说
                Collections.sort(bucketArr.get(i));
            }
    
            //将桶中元素赋值到原序列
            int index;
            if(ascending){
                index=0;
            }else{
                index=arr.length-1;
            }
    
            for(int i=0;i<bucketArr.size();i++){
                for(int j= 0;j<bucketArr.get(i).size();j++){
                    arr[index] = bucketArr.get(i).get(j);
                    if(ascending){
                        index++;
                    }else{
                        index--;
                    }
                }
    
            }
    
        }
    }
    

    基数排序

    简单解释:
    首先说一下,我发现好多人写的基数排序只能排序正整数,其实只要处理下就可以排序含有负数的了,就是我们排序前先把所有的数整体变大(就是减上最小的负数,也就是加了),都变成正数,然后排序好之后,在减下来(加上最小的负数,也就减了)就好了。
    基数排序就是按数位排序可分为LSD(从最低位[也就是个位]开始排序)和MSD(从最高位开始排序),下面写的事LSD基数排序。
    基数排序就是把数按位考虑,让后我们一位数只能是[0,9],就是我们在考虑某位(个位、百位· · ·)的时候就只看这个位的数,放到在[0,9]相应的位置,然后顺序取出,最后再按其它位这样操作(上面说了要不从低位开始到高位,要不就是从高位到低位)

    完整代码:

    package com.keafmd.Sequence;
    
    /**
     * Keafmd
     *
     * @ClassName: RadixSort
     * @Description: 基数排序
     * @author: 牛哄哄的柯南
     * @date: 2021-06-24 14:32
     */
    public class RadixSort {
        public static void radixSort(int[] arr){
            radixSort(arr,true);
        }
        public static void radixSort(int[]arr,boolean ascending){
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            //求出最大值、最小值
            for (int i = 0; i < arr.length; i++) {
                max = Math.max(max, arr[i]);
                min = Math.min(min, arr[i]);
            }
            if (min<0) {	//如果最小值小于0,那么把每个数都减去最小值,这样可以保证最小的数是0
                for (int i = 0; i < arr.length; i++) {
                    arr[i] -= min;
                }
                max -= min; //max也要处理!
            }
            //很巧妙求出最大的数有多少位
            int maxLength = (max+"").length();
            int[][] bucket = new int[10][arr.length]; //一个二维数组,一维代表0到9,二维存放符合数
            int[] bucketElementCount = new int[10]; // 用于记录0到9某位存在数字的个数
            for (int i = 0 ,n = 1 ; i < maxLength ; i++,n*=10) { //个位 十位 百位 这样遍历
                for (int j = 0; j < arr.length ; j++) {
                    int value = arr[j]/n % 10;
                    bucket[value][bucketElementCount[value]] = arr[j];
                    bucketElementCount[value]++;
                }
    
                //升序
                if(ascending) {
                    int index = 0;
                    //从左到右,从下到上取出每个数
                    for (int j = 0; j < bucketElementCount.length; j++) {
                        if (bucketElementCount[j] != 0) {
                            for (int k = 0; k < bucketElementCount[j]; k++) {
                                arr[index] = bucket[j][k];
                                index++;
                            }
                        }
                        bucketElementCount[j] = 0;
                    }
                }else { // 降序
                    int index=0;
                    //从右到左,从下到上取出每个数
                    for (int j = bucketElementCount.length-1; j >=0; j--) {
                        if (bucketElementCount[j] != 0) {
                            for (int k = 0; k <bucketElementCount[j]; k++) {
                                arr[index] = bucket[j][k];
                                index++;
                            }
                        }
                        bucketElementCount[j] = 0;
                    }
                }
    
    
                /*for (int i1 = 0; i1 < arr.length; i1++) {
                    System.out.print(arr[i1]+" ");
                }
                System.out.println();*/
    
    
    
            }
            if (min<0){
                for (int i = 0; i < arr.length ; i++) {
                    arr[i] += min;
                }
            }
    
        }
    }
    

    完整测试类

    package com.keafmd.Sequence;
    
    import java.util.*;
    import java.util.stream.IntStream;
    import java.util.stream.Stream;
    
    /**
     * Keafmd
     *
     * @ClassName: Sort
     * @Description: 十大排序算法测试类
     * @author: 牛哄哄的柯南
     * @date: 2021-06-16 21:27
     */
    public class Sort {
    
    
        public static void main(String[] args) {
    
            int[] nums = {12, 4, 25, 47, 58, 34, 25, 9, 99, 26, 1, -13, 162, 10093, -66, -1};
    //        int[] nums = {12, 43,56,42,26,11};
            int[] temparr;
    
            //利用系统Collections.sort方法进行对比
    
            //将int数组转换为Integer数组
            //1、先将int数组转换为数值流
            temparr = nums.clone();
            IntStream stream = Arrays.stream(temparr);
            //2、流中的元素全部装箱,转换为流 ---->int转为Integer
            Stream<Integer> integerStream = stream.boxed();
            //3、将流转换为数组
            Integer[] integers = integerStream.toArray(Integer[]::new);
            //把数组转为List
            List<Integer> tempList = new ArrayList<>(Arrays.asList(integers));
            //使用Collections.sort()排序
            System.out.println("使用系统的Collections.sort()的对比:");
    
            //Collections.sort
            Collections.sort(tempList, new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1-o2;
                    //return o2-o1;
                }
            });
    
            //tempList.sort 也可以排序
           /* tempList.sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    //return o1-o2;
                    return o2-o1;
                }
            });*/
    
            //遍历输出结果
            for (Integer integer : tempList) {
                System.out.print(integer+" ");
            }
    
            System.out.println();
    
            //测试冒泡排序
            System.out.println("测试冒泡排序:");
            temparr = nums.clone();
    
            BubbleSort.bubbleSort(temparr);
    
            //降序
            //BubbleSort.bubbleSort(temparr,false);
    
            for (int i = 0; i < temparr.length; i++) {
                System.out.print(temparr[i] + " ");
            }
            System.out.println();
    
            //测试快速排序
            System.out.println("测试快速排序:");
            temparr = nums.clone();
            QuickSort.quickSort(temparr);
            //QuickSort.quickSort(temparr,false);
            for (int i = 0; i < temparr.length; i++) {
                System.out.print(temparr[i] + " ");
            }
            System.out.println();
    
            //测试直接选择排序
            System.out.println("测试直接选择排序:");
            temparr = nums.clone();
            SelectSort.selectSort(temparr);
            //SelectSort.selectSort(temparr,false);
            for (int i = 0; i < temparr.length; i++) {
                System.out.print(temparr[i] + " ");
            }
            System.out.println();
    
            //测试堆排序
            System.out.println("测试堆排序:");
            temparr = nums.clone();
            HeapSort.heapSort(temparr);
            //HeapSort.heapSort(temparr,false);
            for (int i = 0; i < temparr.length; i++) {
                System.out.print(temparr[i] + " ");
            }
            System.out.println();
    
            //测试归并排序
            System.out.println("测试归并排序:");
            temparr = nums.clone();
            MergeSort.mergeSort(temparr);
            //MergeSort.mergeSort(temparr,false);
            for (int i = 0; i < temparr.length; i++) {
                System.out.print(temparr[i] + " ");
            }
            System.out.println();
    
            //测试插入排序
            System.out.println("测试插入排序:");
            temparr = nums.clone();
            StraghtInsertSort.straghtInsertSort(temparr);
            //StraghtInsertSort.straghtInsertSort(temparr,false);
            for (int i = 0; i < temparr.length; i++) {
                System.out.print(temparr[i] + " ");
            }
            System.out.println();
    
    
            //测试希尔排序
            System.out.println("测试希尔排序:");
            temparr = nums.clone();
            ShellSort.shellSort(temparr);
            //ShellSort.shellSort(temparr,false);
            for (int i = 0; i < temparr.length; i++) {
                System.out.print(temparr[i] + " ");
            }
            System.out.println();
    
    
            //测试计数排序
            System.out.println("测试计数排序:");
            temparr = nums.clone();
            CountSort.countSort(temparr);
            //CountSort.countSort(temparr,false);
            for (int i = 0; i < temparr.length; i++) {
                System.out.print(temparr[i] + " ");
            }
            System.out.println();
    
    
            //测试桶排序
            System.out.println("测试桶排序:");
            temparr = nums.clone();
            BucketSort.bucketSort(temparr);
            //BucketSort.bucketSort(temparr,false);
            for (int i = 0; i < temparr.length; i++) {
                System.out.print(temparr[i] + " ");
            }
            System.out.println();
    
            //测试基数排序
            System.out.println("测试基数排序:");
            temparr = nums.clone();
            RadixSort.radixSort(temparr);
            //RadixSort.radixSort(temparr,false);
            for (int i = 0; i < temparr.length; i++) {
                System.out.print(temparr[i] + " ");
            }
            System.out.println();
    
        }
    
    }
    

    每天进步一点点!
    不进则退!

    版权声明:
    原创博主:牛哄哄的柯南
    博主原文链接:https://keafmd.blog.csdn.net/

    看完如果对你有帮助,感谢点赞支持!
    如果你是电脑端,看到右下角的 “一键三连” 了吗,没错点它[哈哈]

    在这里插入图片描述
    加油!

    共同努力!

    Keafmd

    展开全文
  • 八大排序算法(C语言实现)

    万次阅读 多人点赞 2021-05-09 13:50:26
    文章目录插入排序插入排序希尔排序选择排序选择排序排序交换排序冒泡排序快速排序并归排序并归排序 插入排序 插入排序 希尔排序 选择排序 选择排序排序 交换排序 冒泡排序 快速排序 并归排序 并归排序 ...


    本次内容大纲:
    在这里插入图片描述
    注:下列八大排序的代码均以排升序为例。

    直接插入排序

    动图演示:
    在这里插入图片描述
     插入排序,又叫直接插入排序。实际中,我们玩扑克牌的时候,就用了插入排序的思想。
    基本思想:
     在待排序的元素中,假设前n-1个元素已有序,现将第n个元素插入到前面已经排好的序列中,使得前n个元素有序。按照此法对所有元素进行插入,直到整个序列有序。

     但我们并不能确定待排元素中究竟哪一部分是有序的,所以我们一开始只能认为第一个元素是有序的,依次将其后面的元素插入到这个有序序列中来,直到整个序列有序为止。
    在这里插入图片描述
    代码:

    //插入排序
    void InsertSort(int* a, int n)
    {
    	int i = 0;
    	for (i = 0; i < n - 1; i++)
    	{
    		int end = i;//记录有序序列的最后一个元素的下标
    		int tmp = a[end + 1];//待插入的元素
    		while (end >= 0)
    		{
    			if (tmp < a[end])//还需继续比较
    			{
    				a[end + 1] = a[end];
    				end--;
    			}
    			else//找到应插入的位置
    			{
    				break;
    			}
    		}
    		a[end + 1] = tmp;
    		//代码执行到此位置有两种情况:
    		//1.待插入元素找到应插入位置(break跳出循环到此)。
    		//2.待插入元素比当前有序序列中的所有元素都小(while循环结束后到此)。
    	}
    }
    

    时间复杂度: O ( N 2 ) O(N^2) O(N2)  空间复杂度: O ( 1 ) O(1) O(1)

    希尔排序

    动图演示:
    在这里插入图片描述
     希尔排序是按其设计者希尔的名字命名的,该算法由希尔1959年公布。希尔可以说是一个脑洞非常大的人,他对普通插入排序的时间复杂度进行分析,得出了以下结论:
     1.普通插入排序的时间复杂度最坏情况下为O(N2),此时待排序列为逆序,或者说接近逆序。
     2.普通插入排序的时间复杂度最好情况下为O(N),此时待排序列为升序,或者说接近升序。

    于是希尔就想:若是能先将待排序列进行一次预排序,使待排序列接近有序(接近我们想要的顺序),然后再对该序列进行一次直接插入排序。因为此时直接插入排序的时间复杂度为O(N),那么只要控制预排序阶段的时间复杂度不超过O(N2),那么整体的时间复杂度就比直接插入排序的时间复杂度低了。
    在这里插入图片描述
    希尔排序,又称缩小增量法。其基本思想是:
     1.先选定一个小于N的整数gap作为第一增量,然后将所有距离为gap的元素分在同一组,并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量,重复上述操作…
     2.当增量的大小减到1时,就相当于整个序列被分到一组,进行一次直接插入排序,排序完成。

    问题:为什么要让gap由大到小呢?
    answer:gap越大,数据挪动得越快;gap越小,数据挪动得越慢。前期让gap较大,可以让数据更快得移动到自己对应的位置附近,减少挪动次数。

    注:一般情况下,取序列的一半作为增量,然后依次减半,直到增量为1(也可自己设置)。

    举个例子分析一下:
     现在我们用希尔排序对该序列进行排序。
    在这里插入图片描述
     我们用序列长度的一半作为第一次排序时gap的值,此时相隔距离为5的元素被分为一组(共分了5组,每组有2个元素),然后分别对每一组进行直接插入排序。
    在这里插入图片描述
     gap的值折半,此时相隔距离为2的元素被分为一组(共分了2组,每组有5个元素),然后再分别对每一组进行直接插入排序。
    在这里插入图片描述
     gap的值再次减半,此时gap减为1,即整个序列被分为一组,进行一次直接插入排序。
    在这里插入图片描述
     该题中,前两趟就是希尔排序的预排序,最后一趟就是希尔排序的直接插入排序。

    代码:

    //希尔排序
    void ShellSort(int* a, int n)
    {
    	int gap = n;
    	while (gap > 1)
    	{
    		gap = gap / 2;//gap折半
    		int i = 0;
    		//进行一趟排序
    		for (i = 0; i < n - gap; i++)
    		{
    			int end = i;
    			int tmp = a[end + gap];
    			while (end >= 0)
    			{
    				if (tmp < a[end])
    				{
    					a[end + gap] = a[end];
    					end -= gap;
    				}
    				else
    				{
    					break;
    				}
    			}
    			a[end + gap] = tmp;
    		}
    	}
    }
    

    时间复杂度: O ( N l o g N ) O(NlogN) O(NlogN)  空间复杂度: O ( 1 ) O(1) O(1)

    平均时间复杂度: O ( N 1.3 ) O(N^{1.3}) O(N1.3)

    选择排序

    动图演示:
    在这里插入图片描述
     选择排序,即每次从待排序列中选出一个最小值,然后放在序列的起始位置,直到全部待排数据排完即可。

    代码:

    //选择排序(一次选一个数)
    void SelectSort(int* a, int n)
    {
    	int i = 0;
    	for (i = 0; i < n; i++)//i代表参与该趟选择排序的第一个元素的下标
    	{
    		int start = i;
    		int min = start;//记录最小元素的下标
    		while (start < n)
    		{
    			if (a[start] < a[min])
    				min = start;//最小值的下标更新
    			start++;
    		}
    		Swap(&a[i], &a[min]);//最小值与参与该趟选择排序的第一个元素交换位置
    	}
    }
    

    时间复杂度: O ( N 2 ) O(N^2) O(N2)  空间复杂度: O ( 1 ) O(1) O(1)

     实际上,我们可以一趟选出两个值,一个最大值一个最小值,然后将其放在序列开头和末尾,这样可以使选择排序的效率快一倍。

    代码:

    //选择排序(一次选两个数)
    void SelectSort(int* a, int n)
    {
    	int left = 0;//记录参与该趟选择排序的第一个元素的下标
    	int right = n - 1;//记录参与该趟选择排序的最后一个元素的下标
    	while (left < right)
    	{
    		int minIndex = left;//记录最小元素的下标
    		int maxIndex = left;//记录最大元素的下标
    		int i = 0;
    		//找出最大值及最小值的下标
    		for (i = left; i <= right; i++)
    		{
    			if (a[i] < a[minIndex])
    				minIndex = i;
    			if (a[i]>a[maxIndex])
    				maxIndex = i;
    		}
    		//将最大值和最小值放在序列开头和末尾
    		Swap(&a[minIndex], &a[left]);
    		if (left == maxIndex)
    		{
    			maxIndex = minIndex;//防止最大值位于序列开头,被最小值交换
    		}
    		Swap(&a[maxIndex], &a[right]);
    		left++;
    		right--;
    	}
    }
    

    时间复杂度: O ( N 2 ) O(N^2) O(N2)  空间复杂度: O ( 1 ) O(1) O(1)

    堆排序

     要学习堆排序,首先要学习堆的向下调整算法,因为要用堆排序,你首先得建堆,而建堆需要执行多次堆的向下调整算法。

    堆的向下调整算法(使用前提):
     若想将其调整为小堆,那么根结点的左右子树必须都为小堆。
     若想将其调整为大堆,那么根结点的左右子树必须都为大堆。
    在这里插入图片描述
    向下调整算法的基本思想(以建大堆为例):
     1.从根结点处开始,选出左右孩子中值较大的孩子。
     2.让大的孩子与其父亲进行比较。
     若大的孩子比父亲还大,则该孩子与其父亲的位置进行交换。并将原来大的孩子的位置当成父亲继续向下进行调整,直到调整到叶子结点为止。
     若大的孩子比父亲小,则不需处理了,调整完成,整个树已经是大堆了。

    图片示例:
    在这里插入图片描述
    堆的向下调整算法代码:

    //堆的向下调整算法
    void AdjustDown(int* a, int n, int root)
    {
    	int parent = root;
    	int child = 2 * parent + 1;//假设左孩子较大
    	while (child < n)
    	{
    		if (child + 1 < n&&a[child + 1] > a[child])//右孩子存在,并且比左孩子大
    		{
    			child++;//左右孩子的较大值
    		}
    		if (a[child] > a[parent])
    		{
    			Swap(&a[child], &a[parent]);
    			parent = child;
    			child = 2 * parent + 1;
    		}
    		else//已成堆
    		{
    			break;
    		}
    	}
    }
    

     使用堆的向下调整算法,最坏的情况下(即一直需要交换结点),需要循环的次数为:h - 1次(h为树的高度)。而h = log2(N+1)(N为树的总结点数)。所以堆的向下调整算法的时间复杂度为:O(logN)

     上面说到,使用堆的向下调整算法需要满足其根结点的左右子树均为大堆或是小堆才行,那么如何才能将一个任意树调整为堆呢?
     答案很简单,我们只需要从倒数第一个非叶子结点开始,从后往前,按下标,依次作为根去向下调整即可。
    在这里插入图片描述
    建堆代码:

    	//建堆
    	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    	{
    		AdjustDown(php->a, php->size, i);
    	}
    

    那么建堆的时间复杂度又是多少呢?
     当结点数无穷大时,完全二叉树与其层数相同的满二叉树相比较来说,它们相差的结点数可以忽略不计,所以计算时间复杂度的时候我们可以将完全二叉树看作与其层数相同的满二叉树来进行计算。
    在这里插入图片描述
    我们计算建堆过程中总共交换的次数:
    T ( n ) = 1 × ( h − 1 ) + 2 × ( h − 2 ) + . . . + 2 h − 3 × 2 + 2 h − 2 × 1 T(n) = 1\times(h-1) + 2\times(h-2) + ... + 2^{h-3}\times2 + 2^{h-2}\times1 T(n)=1×(h1)+2×(h2)+...+2h3×2+2h2×1
    两边同时乘2得:
    2 T ( n ) = 2 × ( h − 1 ) + 2 2 × ( h − 2 ) + . . . + 2 h − 2 × 2 + 2 h − 1 × 1 2T(n) = 2\times(h-1) + 2^2\times(h-2) + ... + 2^{h-2}\times2 + 2^{h-1}\times1 2T(n)=2×(h1)+22×(h2)+...+2h2×2+2h1×1
    两式相减得:
    T ( n ) = 1 − h + 2 1 + 2 2 + . . . + 2 h − 2 + 2 h − 1 T(n)=1-h+2^1+2^2+...+2^{h-2}+2^{h-1} T(n)=1h+21+22+...+2h2+2h1
    运用等比数列求和得:
    T ( n ) = 2 h − h − 1 T(n)=2^h-h-1 T(n)=2hh1
    由二叉树的性质,有 N = 2 h − 1 N=2^h-1 N=2h1 h = log ⁡ 2 ( N + 1 ) h=\log_2(N+1) h=log2(N+1),于是
    T ( n ) = N − log ⁡ 2 ( N + 1 ) T(n)=N-\log_2(N+1) T(n)=Nlog2(N+1)
    用大O的渐进表示法:
    T ( n ) = O ( N ) T(n)=O(N) T(n)=O(N)

    总结一下:
     堆的向下调整算法的时间复杂度: T ( n ) = O ( log ⁡ N ) T(n)=O(\log N) T(n)=O(logN)
     建堆的时间复杂度: T ( n ) = O ( N ) T(n)=O(N) T(n)=O(N)

    那么堆建好后,如何进行堆排序呢?
    步骤如下:
     1、将堆顶数据与堆的最后一个数据交换,然后对根位置进行一次堆的向下调整,但是调整时被交换到最后的那个最大的数不参与向下调整。
     2、完成步骤1后,这棵树除最后一个数之外,其余数又成一个大堆,然后又将堆顶数据与堆的最后一个数据交换,这样一来,第二大的数就被放到了倒数第二个位置上,然后该数又不参与堆的向下调整…反复执行下去,直到堆中只有一个数据时便结束。此时该序列就是一个升序。

    堆排序代码:

    //堆排序
    void HeapSort(int* a, int n)
    {
    	//排升序,建大堆
    	//从第一个非叶子结点开始向下调整,一直到根
    	int i = 0;
    	for (i = (n - 1 - 1) / 2; i >= 0; i--)
    	{
    		AdjustDown(a, n, i);
    	}
    	int end = n - 1;//记录堆的最后一个数据的下标
    	while (end)
    	{
    		Swap(&a[0], &a[end]);//将堆顶的数据和堆的最后一个数据交换
    		AdjustDown(a, end, 0);//对根进行一次向下调整
    		end--;//堆的最后一个数据的下标减一
    	}
    }
    

    时间复杂度: O ( N l o g N ) O(NlogN) O(NlogN)  空间复杂度: O ( 1 ) O(1) O(1)

    冒泡排序

    动图演示:
    在这里插入图片描述
    冒泡排序,该排序的命名非常形象,即一个个将气泡冒出。冒泡排序一趟冒出一个最大(或最小)值。
    在这里插入图片描述
    代码:

    //冒泡排序
    void BubbleSort(int* a, int n)
    {
    	int end = 0;
    	for (end = n - 1; end >= 0; end--)
    	{
    		int exchange = 0;//记录该趟冒泡排序是否进行过交换
    		int i = 0;
    		for (i = 0; i < end; i++)
    		{
    			if (a[i]>a[i + 1])
    			{
    				Swap(&a[i], &a[i + 1]);
    				exchange = 1;
    			}
    		}
    		if (exchange == 0)//该趟冒泡排序没有进行过交换,已有序
    			break;
    	}
    }
    

    时间复杂度: O ( N 2 ) O(N^2) O(N2)  空间复杂度: O ( 1 ) O(1) O(1)

    快速排序

    快速排序是公认的排序之王,快速排序是Hoare于1962年提出的一种二叉树结构的交换排序算法,其基本思想为:
     任取待排序元素序列中的某元素作为基准值,按照该基准值将待排序列分为两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后左右序列重复该过程,直到所有元素都排列在相应位置上为止。

    对于如何按照基准值将待排序列分为两子序列,常见的方式有:
     1、Hoare版本
     2、挖坑法
     3、前后指针法

    递归实现

    Hoare版本

    单趟的动图演示:
    在这里插入图片描述
    Hoare版本的单趟排序的基本步骤如下:
     1、选出一个key,一般是最左边或是最右边的。
     2、定义一个L和一个R,L从左向右走,R从右向左走。(需要注意的是:若选择最左边的数据作为key,则需要R先走;若选择最右边的数据作为key,则需要L先走)。
     3、在走的过程中,若R遇到小于key的数,则停下,L开始走,直到L遇到一个大于key的数时,将L和R的内容交换,R再次开始走,如此进行下去,直到L和R最终相遇,此时将相遇点的内容与key交换即可。(选取最左边的值作为key)

     经过一次单趟排序,最终使得key左边的数据全部都小于key,key右边的数据全部都大于key。

     然后我们在将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作,因为这种序列可以认为是有序的。

    代码:

    //快速排序(Hoare版本)
    void QuickSort1(int* a, int begin, int end)
    {
    	if (begin >= end)//当只有一个数据或是序列不存在时,不需要进行操作
    		return;
    		
    	int left = begin;//L
    	int right = end;//R
    	int keyi = left;//key的下标
    	while (left < right)
    	{
    		//right先走,找小
    		while (left < right&&a[right] >= a[keyi])
    		{
    			right--;
    		}
    		//left后走,找大
    		while (left < right&&a[left] <= a[keyi])
    		{
    			left++;
    		}
    		if (left < right)//交换left和right的值
    		{
    			Swap(&a[left], &a[right]);
    		}
    	}
    	int meeti = left;//L和R的相遇点
    	Swap(&a[keyi], &a[meeti]);//交换key和相遇点的值
    
    	QuickSort1(a, begin, meeti - 1);//key的左序列进行此操作
    	QuickSort1(a, meeti + 1, end);//key的右序列进行此操作
    }
    

    时间复杂度: O ( N l o g N ) O(NlogN) O(NlogN)

    挖坑法

    单趟的动图演示:
    在这里插入图片描述
    挖坑法的单趟排序的基本步骤如下:
     1、选出一个数据(一般是最左边或是最右边的)存放在key变量中,在该数据位置形成一个坑。
     2、还是定义一个L和一个R,L从左向右走,R从右向左走。(若在最左边挖坑,则需要R先走;若在最右边挖坑,则需要L先走)。
     3、在走的过程中,若R遇到小于key的数,则将该数抛入坑位,并在此处形成一个坑位,这时L再向后走,若遇到大于key的数,则将其抛入坑位,又形成一个坑位,如此循环下去,直到最终L和R相遇,这时将key抛入坑位即可。(选取最左边的作为坑位)

     经过一次单趟排序,最终也使得key左边的数据全部都小于key,key右边的数据全部都大于key。

     然后也是将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作。

    代码:

    //快速排序(挖坑法)
    void QuickSort2(int* a, int begin, int end)
    {
    	if (begin >= end)//当只有一个数据或是序列不存在时,不需要进行操作
    		return;
    
    	int left = begin;//L
    	int right = end;//R
    	int key = a[left];//在最左边形成一个坑位
    	while (left < right)
    	{
    		//right向左,找小
    		while (left < right&&a[right] >= key)
    		{
    			right--;
    		}
    		//填坑
    		a[left] = a[right];
    		//left向右,找大
    		while (left < right&&a[left] <= key)
    		{
    			left++;
    		}
    		//填坑
    		a[right] = a[left];
    	}
    	int meeti = left;//L和R的相遇点
    	a[meeti] = key;//将key抛入坑位
    
    	QuickSort2(a, begin, meeti - 1);//key的左序列进行此操作
    	QuickSort2(a, meeti + 1, end);//key的右序列进行此操作
    }
    

    时间复杂度: O ( N l o g N ) O(NlogN) O(NlogN)

    前后指针法

    单趟的动图演示:
    在这里插入图片描述
    前后指针法的单趟排序的基本步骤如下:
     1、选出一个key,一般是最左边或是最右边的。
     2、起始时,prev指针指向序列开头,cur指针指向prev+1。
     3、若cur指向的内容小于key,则prev先向后移动一位,然后交换prev和cur指针指向的内容,然后cur指针++;若cur指向的内容大于key,则cur指针直接++。如此进行下去,直到cur指针越界,此时将key和prev指针指向的内容交换即可。

     经过一次单趟排序,最终也能使得key左边的数据全部都小于key,key右边的数据全部都大于key。

     然后也还是将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作。

    代码:

    //快速排序(前后指针法)
    void QuickSort3(int* a, int begin, int end)
    {
    	if (begin >= end)//当只有一个数据或是序列不存在时,不需要进行操作
    		return;
    
    	//三数取中
    	int midIndex = GetMidIndex(a, begin, end);
    	Swap(&a[begin], &a[midIndex]);
    
    	int prev = begin;
    	int cur = begin + 1;
    	int keyi = begin;
    	while (cur <= end)//当cur未越界时继续
    	{
    		if (a[cur] < a[keyi] && ++prev != cur)//cur指向的内容小于key
    		{
    			Swap(&a[prev], &a[cur]);
    		}
    		cur++;
    	}
    	int meeti = prev;//cur越界时,prev的位置
    	Swap(&a[keyi], &a[meeti]);//交换key和prev指针指向的内容
    
    	QuickSort3(a, begin, meeti - 1);//key的左序列进行此操作
    	QuickSort3(a, meeti + 1, end);//key的右序列进行此操作
    }
    

    时间复杂度: O ( N l o g N ) O(NlogN) O(NlogN)

    非递归实现

     当我们需要将一个用递归实现的算法改为非递归时,一般需要借用一个数据结构,那就是栈。将Hoare版本、挖坑法以及前后指针法的快速排序改为非递归版本,其实主体思想一致,只是调用的单趟排序的算法不同而已。
     于是我们可以先将Hoare版本、挖坑法和前后指针法的单趟排序单独封装起来。然后写一个非递归的快速排序,在函数内部调用单趟排序的函数即可。

    Hoare版本

    Hoare版本的单趟排序代码:

    //Hoare版本(单趟排序)
    int PartSort1(int* a, int left, int right)
    {
    	int keyi = left;//key的下标
    	while (left < right)
    	{
    		//right走,找小
    		while (left < right&&a[right] >= a[keyi])
    		{
    			right--;
    		}
    		//left先走,找大
    		while (left < right&&a[left] <= a[keyi])
    		{
    			left++;
    		}
    		if (left < right)
    		{
    			Swap(&a[left], &a[right]);//交换left和right的值
    		}
    	}
    	int meeti = left;//L和R的相遇点
    	Swap(&a[keyi], &a[meeti]);//交换key和相遇点的值
    	return meeti;//返回相遇点,即key的当前位置
    }
    

    挖坑法

    挖坑法的单趟排序代码:

    //挖坑法(单趟排序)
    int PartSort2(int* a, int left, int right)
    {
    	int key = a[left];//在最左边形成一个坑位
    	while (left < right)
    	{
    		//right向左,找小
    		while (left < right&&a[right] >= key)
    		{
    			right--;
    		}
    		//填坑
    		a[left] = a[right];
    		//left向右,找大
    		while (left < right&&a[left] <= key)
    		{
    			left++;
    		}
    		//填坑
    		a[right] = a[left];
    	}
    	int meeti = left;//L和R的相遇点
    	a[meeti] = key;//将key抛入坑位
    	return meeti;//返回key的当前位置
    }
    

    前后指针法

    前后指针法的单趟排序代码:

    //前后指针法(单趟排序)
    int PartSort3(int* a, int left, int right)
    {
    	int prev = left;
    	int cur = left + 1;
    	int keyi = left;
    	while (cur <= right)//当cur未越界时继续
    	{
    		if (a[cur] < a[keyi] && ++prev != cur)//cur指向的内容小于key
    		{
    			Swap(&a[prev], &a[cur]);
    		}
    		cur++;
    	}
    	int meeti = prev;//cur越界时,prev的位置
    	Swap(&a[keyi], &a[meeti]);//交换key和prev指针指向的内容
    	return meeti;//返回key的当前位置
    }
    

    快速排序的非递归算法基本思路:
     1、先将待排序列的第一个元素的下标和最后一个元素的下标入栈。
     2、当栈不为空时,读取栈中的信息(一次读取两个:一个是L,另一个是R),然后调用某一版本的单趟排序,排完后获得了key的下标,然后判断key的左序列和右序列是否还需要排序,若还需要排序,就将相应序列的L和R入栈;若不需排序了(序列只有一个元素或是不存在),就不需要将该序列的信息入栈。
     3、反复执行步骤2,直到栈为空为止。

    代码:

    //快速排序(非递归实现)
    void QuickSortNonR(int* a, int begin, int end)
    {
    	Stack st;//创建栈
    	StackInit(&st);//初始化栈
    	StackPush(&st, begin);//待排序列的L
    	StackPush(&st, end);//待排序列的R
    	while (!StackEmpty(&st))
    	{
    		int right = StackTop(&st);//读取R
    		StackPop(&st);//出栈
    		int left = StackTop(&st);//读取L
    		StackPop(&st);//出栈
    		//该处调用的是Hoare版本的单趟排序
    		int keyi = PartSort1(a, left, right);
    		if (left < keyi - 1)//该序列的左序列还需要排序
    		{
    			StackPush(&st, left);//左序列的L入栈
    			StackPush(&st, keyi - 1);//左序列的R入栈
    		}
    		if (keyi + 1 < right)// 该序列的右序列还需要排序
    		{
    			StackPush(&st, keyi + 1);//右序列的L入栈
    			StackPush(&st, right);//右序列的R入栈
    		}
    	}
    	StackDestroy(&st);//销毁栈
    }
    

    时间复杂度: O ( N l o g N ) O(NlogN) O(NlogN)

    快速排序的两个优化

    三数取中

     快速排序的时间复杂度是O(NlogN),是我们在理想情况下计算的结果。在理想情况下,我们每次进行完单趟排序后,key的左序列与右序列的长度都相同:
    在这里插入图片描述
     若每趟排序所选的key都正好是该序列的中间值,即单趟排序结束后key位于序列正中间,那么快速排序的时间复杂度就是O(NlogN)。

     可是谁能保证你每次选取的key都是正中间的那个数呢?当待排序列本就是一个有序的序列时,我们若是依然每次都选取最左边或是最右边的数作为key,那么快速排序的效率将达到最低:
    在这里插入图片描述
     可以看到,这种情况下,快速排序的时间复杂度退化为O(N2)。其实,对快速排序效率影响最大的就是选取的key,若选取的key越接近中间位置,则则效率越高。

    为了避免这种极端情况的发生,于是出现了三数取中:
     三数取中,当中的三数指的是:最左边的数、最右边的数以及中间位置的数。三数取中就是取这三个数当中,值的大小居中的那个数作为该趟排序的key。这就确保了我们所选取的数不会是序列中的最大或是最小值了。

    代码:

    //三数取中
    int GetMidIndex(int* a, int left, int right)
    {
    	int mid = left + (right - left) / 2;
    	if (a[mid] > a[left])
    	{
    		if (a[mid] < a[right])
    			return mid;
    		else if (a[left]>a[right])
    			return left;
    		else
    			return right;
    	}
    	else
    	{
    		if (a[mid] > a[right])
    			return mid;
    		else if (a[left] > a[right])
    			return right;
    		else
    			return left;
    	}
    }
    

    注意:当大小居中的数不在序列的最左或是最右端时,我们不是就以居中数的位置作为key的位置,而是将key的值与最左端的值进行交换,这样key就还是位于最左端了,所写代码就无需改变,而只需在单趟排序代码开头加上以下两句代码即可:

    	int midIndex = GetMidIndex(a, begin, end);//获取大小居中的数的下标
    	Swap(&a[begin], &a[midIndex]);//将该数与序列最左端的数据交换
    	//以下代码保持不变...
    

    小区间优化

     我们可以看到,就算是上面理想状态下的快速排序,也不能避免随着递归的深入,每一层的递归次数会以2倍的形式快速增长。
     为了减少递归树的最后几层递归,我们可以设置一个判断语句,当序列的长度小于某个数的时候就不再进行快速排序,转而使用其他种类的排序。小区间优化若是使用得当的话,会在一定程度上加快快速排序的效率,而且待排序列的长度越长,该效果越明显。

    代码示例:

    //优化后的快速排序
    void QuickSort0(int* a, int begin, int end)
    {
    	if (begin >= end)//当只有一个数据或是序列不存在时,不需要进行操作
    		return;
    
    	if (end - begin + 1 > 20)//可自行调整
    	{
    		//可调用快速排序的单趟排序三种中的任意一种
    		//int keyi = PartSort1(a, begin, end);
    		//int keyi = PartSort2(a, begin, end);
    		int keyi = PartSort3(a, begin, end);
    		QuickSort(a, begin, keyi - 1);//key的左序列进行此操作
    		QuickSort(a, keyi + 1, end);//key的右序列进行此操作
    	}
    	else
    	{
    		//HeapSort(a, end - begin + 1);
    		ShellSort(a, end - begin + 1);//当序列长度小于等于20时,使用希尔排序
    	}
    }
    

    归并排序

    动图演示:
    在这里插入图片描述
     归并排序是采用分治法的一个非常典型的应用。其基本思想是:将已有序的子序合并,从而得到完全有序的序列,即先使每个子序有序,再使子序列段间有序。

     相信大家都知道如何将两个有序序列合为一个有序序列吧:
    在这里插入图片描述
     那么如何得到有序的子序列呢?当序列分解到只有一个元素或是没有元素时,就可以认为是有序了,这时分解就结束了,开始合并:
    在这里插入图片描述

    递归实现

     归并排序,从其思想上看就很适合使用递归来实现,并且用递归实现也比较简单。其间我们需要申请一个与待排序列大小相同的数组用于合并过程两个有序的子序列,合并完毕后再将数据拷贝回原数组。

    代码:

    //归并排序(子函数)
    void _MergeSort(int* a, int left, int right, int* tmp)
    {
    	if (left >= right)//归并结束条件:当只有一个数据或是序列不存在时,不需要再分解
    	{
    		return;
    	}
    	int mid = left + (right - left) / 2;//中间下标
    	_MergeSort(a, left, mid, tmp);//对左序列进行归并
    	_MergeSort(a, mid + 1, right, tmp);//对右序列进行归并
    	int begin1 = left, end1 = mid;
    	int begin2 = mid + 1, end2 = right;
    	//将两段子区间进行归并,归并结果放在tmp中
    	int i = left;
    	while (begin1 <= end1&&begin2 <= end2)
    	{
    		//将较小的数据优先放入tmp
    		if (a[begin1] < a[begin2])
    			tmp[i++] = a[begin1++];
    		else
    			tmp[i++] = a[begin2++];
    	}
    	//当遍历完其中一个区间,将另一个区间剩余的数据直接放到tmp的后面
    	while (begin1 <= end1)
    		tmp[i++] = a[begin1++];
    	while (begin2 <= end2)
    		tmp[i++] = a[begin2++];
    	//归并完后,拷贝回原数组
    	int j = 0;
    	for (j = left; j <= right; j++)
    		a[j] = tmp[j];
    }
    //归并排序(主体函数)
    void MergeSort(int* a, int n)
    {
    	int* tmp = (int*)malloc(sizeof(int)*n);//申请一个与原数组大小相同的空间
    	if (tmp == NULL)
    	{
    		printf("malloc fail\n");
    		exit(-1);
    	}
    	_MergeSort(a, 0, n - 1, tmp);//归并排序
    	free(tmp);//释放空间
    }
    

    时间复杂度: O ( N l o g N ) O(NlogN) O(NlogN)  空间复杂度: O ( N ) O(N) O(N)

    非递归实现

     归并排序的非递归算法并不需要借助栈来完成,我们只需要控制每次参与合并的元素个数即可,最终便能使序列变为有序:
    在这里插入图片描述
     当然,以上例子是一个待排序列长度比较特殊的例子,我们若是想写出一个广泛适用的程序,必定需要考虑到某些极端情况:
    情况一:
     当最后一个小组进行合并时,第二个小区间存在,但是该区间元素个数不够gap个,这时我们需要在合并序列时,对第二个小区间的边界进行控制。
    在这里插入图片描述
    情况二:
     当最后一个小组进行合并时,第二个小区间不存在,此时便不需要对该小组进行合并。
    在这里插入图片描述
    情况三:
     当最后一个小组进行合并时,第二个小区间不存在,并且第一个小区间的元素个数不够gap个,此时也不需要对该小组进行合并。(可与情况二归为一类)
    在这里插入图片描述
     只要把控好这三种特殊情况,写出归并排序的非递归算法便轻而易举了。

    代码:

    //归并排序(子函数)
    void _MergeSortNonR(int* a, int* tmp, int begin1, int end1, int begin2, int end2)
    {
    	int j = begin1;
    	//将两段子区间进行归并,归并结果放在tmp中
    	int i = begin1;
    	while (begin1 <= end1&&begin2 <= end2)
    	{
    		//将较小的数据优先放入tmp
    		if (a[begin1] < a[begin2])
    			tmp[i++] = a[begin1++];
    		else
    			tmp[i++] = a[begin2++];
    	}
    	//当遍历完其中一个区间,将另一个区间剩余的数据直接放到tmp的后面
    	while (begin1 <= end1)
    		tmp[i++] = a[begin1++];
    	while (begin2 <= end2)
    		tmp[i++] = a[begin2++];
    	//归并完后,拷贝回原数组
    	for (; j <= end2; j++)
    		a[j] = tmp[j];
    }
    //归并排序(主体函数)
    void MergeSortNonR(int* a, int n)
    {
    	int* tmp = (int*)malloc(sizeof(int)*n);//申请一个与待排序列大小相同的空间,用于辅助合并序列
    	if (tmp == NULL)
    	{
    		printf("malloc fail\n");
    		exit(-1);
    	}
    	int gap = 1;//需合并的子序列中元素的个数
    	while (gap < n)
    	{
    		int i = 0;
    		for (i = 0; i < n; i += 2 * gap)
    		{
    			int begin1 = i, end1 = i + gap - 1;
    			int begin2 = i + gap, end2 = i + 2 * gap - 1;
    			if (begin2 >= n)//最后一组的第二个小区间不存在或是第一个小区间不够gap个,此时不需要对该小组进行合并
    				break;
    			if (end2 >= n)//最后一组的第二个小区间不够gap个,则第二个小区间的后界变为数组的后界
    				end2 = n - 1;
    			_MergeSortNonR(a, tmp, begin1, end1, begin2, end2);//合并两个有序序列
    		}
    		gap = 2 * gap;//下一趟需合并的子序列中元素的个数翻倍
    	}
    	free(tmp);//释放空间
    }
    

    时间复杂度: O ( N l o g N ) O(NlogN) O(NlogN)  空间复杂度: O ( N ) O(N) O(N)

    外排序

    首先,我先说明一下什么是内排序,什么是外排序:
     内排序:数据量相对少一些,可以放到内存中进行排序。
     外排序:数据量较大,内存中放不下,数据只能放到磁盘文件中,需要排序。

     上面介绍的排序算法均是在内存中进行的,对于数据量庞大的序列,上面介绍的排序算法都束手无策,而归并排序却能胜任这种海量数据的排序。

     假设现在有10亿个整数(4GB)存放在文件A中,需要我们进行排序,而内存一次只能提供512MB空间,归并排序解决该问题的基本思路如下:
     1、每次从文件A中读取八分之一,即512MB到内存中进行排序(内排序),并将排序结果写入到一个文件中,然后再读取八分之一,重复这个过程。那么最终会生成8个各自有序的小文件(A1~A8)。
     2、对生成的8个小文件进行11合并,最终8个文件被合成为4个,然后再11合并,就变成2个文件了,最后再进行一次11合并,就变成1个有序文件了。

    注意:这里将两个文件进行11合并,并不是先将两个文件读入内存然后进行合并,因为内存装不下。这里的11合并是利用文件输入输出函数,从两个文件中各自读取一个数据,然后进行比较,将较小的数据写入到一个新文件中去,然后再读取,再比较,再写入,最终将两个文件中的数据全部写入到另一个文件中去,那么此时这个文件又是一个有序的文件了。
    在这里插入图片描述
    当然,你也可以这样合并文件:
    在这里插入图片描述
    外排序代码示例:

    //将file1文件和file2文件中的数据归并到mfile文件中
    void _MergeFile(const char* file1, const char* file2, const char* mfile)
    {
    	FILE* fout1 = fopen(file1, "r");//打开file1文件
    	if (fout1 == NULL)
    	{
    		printf("打开文件失败\n");
    		exit(-1);
    	}
    
    	FILE* fout2 = fopen(file2, "r");//打开file2文件
    	if (fout2 == NULL)
    	{
    		printf("打开文件失败\n");
    		exit(-1);
    	}
    
    	FILE* fin = fopen(mfile, "w");//打开mfile文件
    	if (fin == NULL)
    	{
    		printf("打开文件失败\n");
    		exit(-1);
    	}
    
    	int num1, num2;
    	int ret1 = fscanf(fout1, "%d\n", &num1);//读取file1文件中的数据
    	int ret2 = fscanf(fout2, "%d\n", &num2);//读取file2文件中的数据
    	while (ret1 != EOF && ret2 != EOF)
    	{
    		//将读取到的较小值写入到mfile文件中,继续从file1和file2中读取数据进行比较
    		if (num1 < num2)
    		{
    			fprintf(fin, "%d\n", num1);
    			ret1 = fscanf(fout1, "%d\n", &num1);
    		}
    		else
    		{
    			fprintf(fin, "%d\n", num2);
    			ret2 = fscanf(fout2, "%d\n", &num2);
    		}
    	}
    	//将file1文件中未读取完的数据写入文件mfile中
    	while (ret1 != EOF)
    	{
    		fprintf(fin, "%d\n", num1);
    		ret1 = fscanf(fout1, "%d\n", &num1);
    	}
    	//将file2文件中未读取完的数据写入文件mfile中
    	while (ret2 != EOF)
    	{
    		fprintf(fin, "%d\n", num2);
    		ret2 = fscanf(fout2, "%d\n", &num2);
    	}
    	fclose(fout1);//关闭file1文件
    	fclose(fout2);//关闭file2文件
    	fclose(fin);//关闭mfile文件
    }
    //将文件中的数据进行排序
    void MergeSortFile(const char* file)
    {
    	FILE* fout = fopen(file, "r");//打开文件
    	if (fout == NULL)
    	{
    		printf("打开文件失败\n");
    		exit(-1);
    	}
    	// 分割成一段一段数据,内存排序后写到小文件中
    	int n = 10;//一次读取10个数据进行内排序
    	int a[10];//读取数据放到数组中,准备进行内排序
    	int i = 0;
    	int num = 0;
    	char subfile[20];//文件名字符串
    	int filei = 1;//储存第filei组内排序后的数据的文件的文件名
    
    	memset(a, 0, sizeof(int)*n);//将数组a的空间置0
    	while (fscanf(fout, "%d\n", &num) != EOF)//从文件中读取数据
    	{
    		if (i < n - 1)//读取前9个数据
    		{
    			a[i++] = num;
    		}
    		else//读取第10个数据
    		{
    			a[i] = num;
    			QuickSort(a, 0, n - 1);//将这10个数据进行快速排序
    			sprintf(subfile, "%d", filei++);//将储存第filei组内排序后的数据的文件的文件名命名为filei
    			FILE* fin = fopen(subfile, "w");//创建一个以字符串subfile[20]为名字的文件并打开
    			if (fin == NULL)
    			{
    				printf("打开文件失败\n");
    				exit(-1);
    			}
    			//将内排序排好的数据写入到subfile文件中
    			for (int i = 0; i < n; i++)
    			{
    				fprintf(fin, "%d\n", a[i]);
    			}
    			fclose(fin);//关闭subfile文件
    
    			i = 0;
    			memset(a, 0, sizeof(int)*n);//将a数组内存置0,准备再次读取10个数据进行内排序
    		}
    	}
    	// 利用互相归并到文件,实现整体有序
    	char mfile[100] = "12";//归并后文件的文件名
    	char file1[100] = "1";//待归并的第一个文件的文件名
    	char file2[100] = "2";//待归并的第二个文件的文件名
    	for (int i = 2; i <= n; ++i)
    	{
    		//将file1文件和file2文件中的数据归并到mfile文件中
    		_MergeFile(file1, file2, mfile);
    
    		strcpy(file1, mfile);//下一次待归并的第一个文件就是上一次归并好的文件
    		sprintf(file2, "%d", i + 1);//上一次待归并的第二个文件的文件名加一,就是下一次待归并的第二个文件的文件名
    		sprintf(mfile, "%s%d", mfile, i + 1);//下一次归并后文件的文件名
    	}
    
    	fclose(fout);//关闭文件
    }
    //主函数
    int main()
    {
    	MergeSortFile("Sort.txt");//将Sort.txt文件中的数据进行排序
    	return 0;
    }
    

    注:代码中使用的是第二种文件合并的方式。

    计数排序

     计数排序,又叫非比较排序。顾名思义,该算法不是通过比较数据的大小来进行排序的,而是通过统计数组中相同元素出现的次数,然后通过统计的结果将序列回收到原来的序列中。

    举个例子:
    在这里插入图片描述
     上列中的映射方法称为绝对映射,即arr数组中的元素是几就在count数组中下标为几的位置++,但这样会造成空间浪费。例如,我们要将数组:1020,1021,1018,进行排序,难道我们要开辟1022个整型空间吗?
     若是使用计数排序,我们应该使用相对映射,简单来说,数组中的最小值就相对于count数组中的0下标,数组中的最大值就相对于count数组中的最后一个下标。这样,对于数组:1020,1021,1018,我们就只需要开辟用于储存4个整型的空间大小了,此时count数组中下标为i的位置记录的实际上是1018+i这个数出现的次数。

    总结:
     绝对映射:count数组中下标为i的位置记录的是arr数组中数字i出现的次数。
     相对映射:count数组中下标为i的位置记录的是arr数组中数字min+i出现的次数。

    注:计数排序只适用于数据范围较集中的序列的排序,若待排序列的数据较分散,则会造成空间浪费,并且计数排序只适用于整型排序,不适用与浮点型排序。

    代码:

    //计数排序
    void CountSort(int* a, int n)
    {
    	int min = a[0];//记录数组中的最小值
    	int max = a[0];//记录数组中的最大值
    	for (int i = 0; i < n; i++)
    	{
    		if (a[i] < min)
    			min = a[i];
    		if (a[i] > max)
    			max = a[i];
    	}
    	int range = max - min + 1;//min和max之间的自然数个数(包括min和max本身)
    	int* count = (int*)calloc(range, sizeof(int));//开辟可储存range个整型的内存空间,并将内存空间置0
    	if (count == NULL)
    	{
    		printf("malloc fail\n");
    		exit(-1);
    	}
    	//统计相同元素出现次数(相对映射)
    	for (int i = 0; i < n; i++)
    	{
    		count[a[i] - min]++;
    	}
    	int i = 0;
    	//根据统计结果将序列回收到原来的序列中
    	for (int j = 0; j < range; j++)
    	{
    		while (count[j]--)
    		{
    			a[i++] = j + min;
    		}
    	}
    	free(count);//释放空间
    }
    

    时间复杂度: O ( N + r a n g e ) O(N+range) O(N+range)  空间复杂度: O ( r a n g e ) O(range) O(range)

    展开全文
  • 【数据结构】八大排序(超详解+附动图+源码)

    万次阅读 多人点赞 2021-11-19 12:45:55
    外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。 这部分主要是内部排序排序讲解都以升序为例。 常见的排序算法: // 排序实现的接口 // 插入排序 void...
  • 十大经典排序算法

    万次阅读 多人点赞 2021-10-21 10:40:42
    稳定排序: 冒泡排序、插入排序、归并排序 非稳定排序: 选择排序、希尔排序、堆排序、快速排序 1、冒泡排序 冒泡排序就是把小的元素往前调或者把大的元素往后调,比较是相邻的两个元素比较,交换也发生在这两...
  • 冒泡排序、选择排序、插入排序、快速排序、希尔排序
  • 程序员那些必须掌握的排序算法(上)

    万次阅读 多人点赞 2019-08-17 16:03:39
    如果有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序...
  • 快速排序法(详解)

    万次阅读 多人点赞 2019-07-01 17:27:49
    假设对以下10个数进行快速排序: 6 1 2 7 9 3 4 5 10 8 我们先模拟快速排序的过程:首先,在这个序列中随便找一个数作为基准数,通常为了方便,以第一个数作为基准数。 6 1 2 ...
  • C++ sort()排序详解

    万次阅读 多人点赞 2020-05-05 22:00:36
    而且我们还需要根据需要去选择相关的排序方法:冒泡排序、快速排序、插入排序、希尔排序、归并排序、选择排序、堆排序、基数排序、桶排序。在选择的过程中也需要我们花费一些时间,所以在明白这些经典排序的情况下再...
  • 八大排序算法(直接插入排序,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,计数排序
  • 之前的文章,我已经把前端需要了解的...现在我们要开始对排序算法部分进行讲解,排序算法顾名思义,就是对一堆杂乱无章的数据按照一定的规则将它们有序地排列在一起。 在讲解排序算法时,大致分成两大类,如下图 本文
  • 算法学习总结(2)——温故十大经典排序算法

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

    千次阅读 2021-07-05 23:28:24
    插入排序分为直接插入排序、折半插入排序、希尔排序(shell sort),后两种是在直接插入排序的改进上而来。 1.直接插入排序 排序思路:假设待排序的元素存放在数组A[1..n]A[1..n]A[1..n]中,在排序过程的某一时刻,...
  • 直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序、快速排序、归并排序、基数排序。 算法复杂度比较: 算法分类 一、直接插入排序 一个插入排序是另一种简单排序,它的思路是:每次从未排好的序列中选出第一...
  • 深处开发岗,其实排序也是绕不开的环节,其中冒泡排序,选择排序,插入排序,归并排序,快速排序,堆排序也是我在秋招以来频繁问到的技术点 排序算法有两块比较重要的知识点 内存消耗 :算法的内存消耗可以通过...
  • 直接选择排序和冒泡排序

    千次阅读 2020-11-27 23:43:49
    直接选择排序 直接选择排序是一种简单的排序算法。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置;再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有...
  • 排序算法(图解详细流程)

    万次阅读 多人点赞 2018-08-04 11:21:17
    排序的时间复杂度O(N*logN),额外空间复杂度O(1),是一个不稳定性的排序 目录 一 准备知识 1.1 大根堆和小根堆 二 堆排序基本步骤 2.1 构造堆 2.2固定最大值再构造堆 三 总结 四代码 一 准备知识 堆的...
  • 冒泡排序(超详细)

    万次阅读 多人点赞 2021-06-11 11:30:32
    1、什么是冒泡排序? 冒泡排序的英文Bubble Sort,是一种最基础的交换排序。之所以叫做冒泡排序,因为每一个元素都可以像小气泡一样,根据自身大小一点一点向数组的一侧移动。 冒泡排序的原理: 每一趟只能确定将...
  • 用 Python 实现十大经典排序算法

    万次阅读 多人点赞 2022-03-10 20:01:01
    10种经典排序算法包括冒泡排序、选择排序、快速排序、归并排序、堆排序、插入排序、希尔排序、计数排序、桶排序、基数排序等。 当然,还有一些其他的排序算法,大家可以继续去研究下。 01冒泡排序 冒泡排序...
  • 在 Python 中,你可以使用sorted()方法或sort()方法对数据进行排序。 在本文中,我将提供sorted()和sort()方法的代码示例,并解释两者之间的区别。 Python 排序列表——如何按降序或升序排序 在 Python 中,你...
  • 十大经典排序算法总结(Java实现+动画)

    万次阅读 多人点赞 2019-06-19 16:26:29
    最近在梳理《数据结构与算法》的内容,在网上看了几篇不错的文章,现在根据自己的理解重新整理一下十大经典排序算法。实际生产中,最好的算法一定是结合数据集本身的特点(大小,长度,是否已经基本有序等等)来选择...
  • stream排序

    万次阅读 2021-12-27 16:16:56
    stream如何排序? 使用stream中sorted方法 怎么使用? 1:创建实体类。2:创建list。3:用list.stream().sorted(); 如图所示: List<Test> list = new ArrayList<>(); Test test = new Test(); test...
  • 本篇文章讲解三个高级排序算法,分别为希尔排序、归并排序、快速排序。虽然它们的思想很复杂,但真的运用得非常得巧妙,我会用丰富的例子以及动图来让大家轻松地理解并掌握。
  • 十大经典排序算法-归并排序算法详解

    万次阅读 多人点赞 2020-06-19 15:23:51
    归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法,归并排序对序列的元素进行逐层折半分组,然后从最小分组开始比较排序,合并成一个大的分组,逐层进行,最终所有的元素都是有序的 2.算法原理 这是一...
  • 0、排序算法说明 0.1 排序的定义 对一序列对象根据某个关键字进行排序。 0.2 术语说明 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面; 不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b...
  • 数据结构:10大经典排序

    千次阅读 多人点赞 2022-02-02 17:53:04
    排序1、冒泡排序2、选择排序3、插入排序4、希尔排序5、快速排序6、归并排序7、堆排序8、计数排序9、桶排序10、基数排序 1、冒泡排序 // 冒泡排序 #include <stdlib.h> #include <stdio.h> // 采用两层...
  • 排序算法:选择排序

    万次阅读 多人点赞 2021-03-29 12:11:32
    1. 什么是选择排序?(摘抄自百度百科) 选择排序(Selection sort)是一种简单直观的排序算法。 它的工作原理是: 第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从...
  • 冒泡排序3.1 排序原理3.2 冒泡排序api设计和代码实现3.3 测试3.4 冒泡排序的时间复杂度分析3.5 冒泡排序优化四. 选择排序4.1 排序原理4.2 选择排序api设计和代码实现4.3 测试4.4 选择排序的时间复杂度分析4.5 选择...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,253,671
精华内容 1,301,468
关键字:

排序

友情链接: multzstyleinterface.rar