八大排序算法

​ 八大排序算法是面试经常考到的,尤其是快排,希尔排序和归并也是经常会让写代码的题目,其实只要用一句话说明了他们的原理我们写起代码就没那么困难。

冒泡排序

思想:有 n 个数我们就进行 n-1 趟排序,每一趟我们都选取最大的一个数放到已经排序的位置即可。

伪代码:两个 For 循环,外层表示要进行的趟数,内层则是找出最大的数,找最大的数的方法就是比较、交换。

时间复杂度:O(n2)

空间复杂度:O(n)

代码:

package Sorting;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class Bubble {

    public static void sort(int[] arr) {
        for (int i=1;i<arr.length-1;++i) {
            for(int j=0;j<arr.length-i;++j) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr,j);
                }
            }
        }
    }

    private static void swap(int[] arr, int j) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
    }

    @Test
    public void test() {
        int[] arr = new int[]{2, 1, 4, 5, 3, 2};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

插入排序

思想:插入排序就是把元素分成两部分,一部分就是有序的,而另外一部分无序。我们每次在无序的集合里面找到一个元素插入到他在有序集合中对应的位置。因此总的来说他就是把一个数据插入到已经排好序的数据中。

####分类:实际上插入排序是一个类别,它里面有很多具体的排序方式。直接插入排序,折半插入排序,希尔排序 ( 又称缩小增量排序 )。他们都是属于稳定排序。

直接插入排序

思想:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列。形象的可以理解为打扑克抓拍的过程,通常我们右手抓牌,没抓一张牌,就放到左手,抓下一张牌后,会把这张牌依次与左手上的牌比较,并把它插入到一个合适的位置(按牌面大小)。

应用优势:插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。

时间复杂度:O(n2)

package Sorting;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class SimpleInsert {
    public void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j > -1 && temp < arr[j]) {
                arr[j + 1] = arr[j];
                --j;
            }
            arr[j + 1] = temp;
        }
    }

    @Test
    public void test(){
        int[] arr = new int[]{5, 3, 2, 6, 8, 1, 3, 0};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

二分插入排序

思想:也就是和上面的简单插入排序一样,只是简单插入排序做了很多的判断,元素到底应该插入哪个位置,而这里我们是使用这般查找来确定位置,因为那一部分是有序的。

时间复杂度:n2

希尔排序

思想:希尔排序的基本思想就是设置一个步长,首先步长是整个元素的长度的一半,这样我们每一个分组只有两个元素在这个分组中我们进行排序,然后我们减小步长也就是再次除以二,继续上面的步骤,最后我们会得到整个元素的集合成为一个分组。

稳定性:不稳定

时间复杂度:n(logn)

package Sorting;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class Shell {
    public void sort(int[] arr) {
        int step = arr.length / 2;
        //这是循环每一个步长
        while (step > 0) {
            //这是循环每一个分组的第一个元素的下标
            for (int i = 0; i <= step; i++) {
                //这是一层简单插入排序
                for (int ptr = i; ptr + step < arr.length; ptr += step) {
                    int temp = arr[ptr + step];
                    int j = ptr;
                    while (j >= 0 && arr[j] > temp) {
                        arr[j + step] = arr[j];
                        j -= step;
                    }
                    arr[j+step] = temp;
                }
            }
            step /= 2;
        }
    }

    @Test
    public void test(){
        int[] arr = new int[]{5, 3, 2, 6, 8, 1, 3, 0};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

简单选择排序

思想:始终选取最小的元素往前面的有序序列中插入

稳定性:不稳定

时间复杂度:O(n2)

package Sorting;

import org.junit.jupiter.api.Test;

public class SimpleSorting {
    void sort(int[] arr) {
        int min;
        for (int i = 0; i < arr.length; i++) {
            min = minIndex(arr, i);
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }

    private int minIndex(int[] arr, int start) {
        int min = start;
        for (int i = start; i < arr.length; i++) {
            min = arr[i] < arr[min] ? i : min;
        }
        return min;
    }

    @Test
    public void fun() {
        int[] arr = new int[]{6, 2, 3, 4, 51, 32, 52, 33};
        sort(arr);
        for (int ele : arr) {
            System.out.printf(ele + " ");
        }
    }
}

快速排序

思想:寻找一个枢轴元素,然后我们把枢轴元素归位,也就是比他小的放在他的左边比他大的放右边,然后继续在他的左边右边选取枢轴元素继续如此进行。

时间复杂度:

稳定性:这就是在我们输入数据基本有序甚至完全有序的时候,这算法退化为冒泡排序,不再是O(n㏒n),而是O(n^2)了。

package Sorting;

import org.junit.jupiter.api.Test;

public class QuickSorting {

    void sort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int center = getMid(arr, start, end);
        sort(arr, start, center - 1);
        sort(arr, center + 1, end);
    }

    void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    int getMid(int[] arr, int start, int end) {
        int temp = arr[start];
        while (start < end) {
            while (start < end && arr[end] >= temp) {
                end--;
            }
            arr[start] = arr[end];


            while (start < end && arr[start] <= temp) {
                start++;
            }
            arr[end] = arr[start];
        }
        arr[start] = temp;
        return start;
    }

    @Test
    public void fun() {
        int[] arr = new int[]{5, 3, 2, 6, 8, 1, 3, 0};
        sort(arr);
        for (int ele : arr) {
            System.out.printf(ele + " ");
        }
    }
}

归并排序

思想:就是先把元素分成两部分,然后对这两部分继续排序,最后进行合并这两部分。这也是一个重要的分治思想归并法。

分治思想:经典的分治(divide-and-conquer)策略(分治法将问题(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起,即分而治之)。

时间复杂度:O(nlogn)

空间复杂度:O(n)

稳定性:稳定

package Sorting;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class Merge {
    public static void sort(int []arr){
        int []temp = new int[arr.length];//在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
        sort(arr,0,arr.length-1,temp);
    }
    private static void sort(int[] arr,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            sort(arr,left,mid,temp);//左边归并排序,使得左子序列有序
            sort(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++];
        }
    }

    @Test
    public void fun() {
        int[] arr = new int[]{5, 3, 2, 6, 8, 1, 3, 0, 9};
        int[] temp = new int[arr.length];
        sort(arr, 0, arr.length - 1, temp);
        System.out.println(Arrays.toString(arr));
    }
}

堆排序

思想:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了

稳定性:不稳定

时间复杂度:O(nlogn)

package Sorting;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class HeapSort {

    public static void sort(int []arr){
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            //从第一个非叶子结点从下至上,从右至左调整结构
            swim(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            swim(arr,0,j);//重新对堆进行调整
        }

    }

    /**
     * 调整大顶堆(仅是调整过程,建立在大顶堆已构建的基础上)
     * @param arr
     * @param i
     * @param length
     */
    public static void swim(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始,也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点,k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    @Test
    public void fun() {
        int[] arr = new int[]{5, 3, 2, 6, 8, 1, 3, 0};
        sort(arr);
        for (int ele : arr) {
            System.out.printf(ele + " ");
        }
    }

}

总结

稳定性:堆排序、快速排序、希尔排序、直接选择排序 不是稳定的排序算法,而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

应用场景:

(1)若n较小(如n≤50),可采用直接插入或直接选择排序。  当记录规模较小时,直接插入排序较好;否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜。 (2)若文件初始状态基本有序(指正序),则应选用直接插人、冒泡或随机的快速排序为宜; (3)若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或归并排序。  快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;  堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。  若要求排序稳定,则可选用归并排序。但前面介绍的从单个记录起进行两两归并的排序算法并不值得提倡,通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子序列,然后再两两归并之。因为直接插入排序是稳定 的,所以改进后的归并排序仍是稳定的。

复杂度:

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我就是马云飞

【数据结构】七大排序算法

排序的相关概念 排序的分类 根据在排序过程中带排序的记录是否全部被放置在内存中,排序分为: 内排序 外排序 1.内排序 内排序是在排序整个过程中,带排序的所有...

214100
来自专栏木子昭的博客

正则 (入门篇)简单来说写好正则表达式的两个要点:写在最后

如果你对正则感兴趣,读完这篇文章,一定会有收获~_^ 简单来说 正则一般代指正则表达式 正则表达式是从"复杂数据"中抽取"有用数据"的公式 ---- 写好正则...

31980
来自专栏编程

八大排序算法总结与java实现

概述 因为健忘,加上对各种排序算法理解不深刻,过段时间面对排序就蒙了。所以决定对我们常见的这几种排序算法进行统一总结。首先罗列一下常见的十大排序算法: ? 请点...

310100
来自专栏菩提树下的杨过

数据结构与算法C#版笔记--排序(Sort)-下

5、堆排序(HeapSort) 在接触“堆排序”前,先回顾一下数据结构C#版笔记--树与二叉树 ,其中提到了“完全二叉树”有一些重要的数学特性: ? 上图就是一...

21650
来自专栏高性能服务器开发

全排列(含递归和非递归的解法)

全排列在近几年各大网络公司的笔试中出现的比较频繁 首先来看看题目是如何要求的(百度迅雷校招笔试题)。 用C++写一个函数, 如 Foo(const char *...

20730
来自专栏木头编程 - moTzxx

PHP常见排序算法整理学习

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u011415782/article/de...

25830
来自专栏老九学堂

嘀 , 嘀嘀 ... 常用排序算法再总结

  这篇文章中再和小伙伴们来探讨一下常用的非比较排序算法:计数排序,基数排序,桶排序。在一定条件下,它们的时间复杂度可以达到O(n)。

13830
来自专栏JetpropelledSnake

Python入门之三元表达式\列表推导式\生成器表达式\递归匿名函数\内置函数

本章目录:     一、三元表达式、列表推导式、生成器表达式     二、递归调用和二分法     三、匿名函数     四、内置函数 ============...

42450
来自专栏QQ音乐前端团队专栏

理解浮点数

相信大家在平常的 JavaScript 开发中,都有遇到过浮点数运算精度误差的问题。

76940
来自专栏菩提树下的杨过

javascript:算法笔记

入门级算法-线性查找-时间复杂度O(n)--相当于算法界中的HelloWorld //线性搜索(入门HelloWorld) //A为数组,x为要...

245100

扫码关注云+社区

领取腾讯云代金券