栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

[排序]稳定性、插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

[排序]稳定性、插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序

目录
  • 稳定性
  • 1.插入排序
    • 1.1思路:
    • 1.2代码
    • 1.3复杂度
    • 1.4.特点:
  • 2.希尔排序
    • 2.1思路
    • 2.2代码
    • 2.3复杂度
    • 2.4特点
  • 3.选择排序
    • 3.1思路
    • 3.2代码
    • 3.3复杂度
  • 4.堆排序
    • 4.1思路
    • 4.2代码
    • 4.3复杂度
  • 5.冒泡排序
    • 5.1思路
    • 5.2代码
    • 5.3复杂度
  • 6.快速排序
    • 6.1思路
    • 6.2代码
    • 6.3复杂度
  • 7.归并排序
    • 7.1思路
    • 7.2代码
    • 7.3复杂度


稳定性

两个相等的数据,如果经过排序后,排序算法能保证其相对位置不发生变化,则我们称该算法是具备稳定性的排序算法。


1.插入排序 1.1思路:

1.将整个队列分为已排序区间和待排序区间
2.每次选择待排序区间的第一个元素,和已排序区间的最后一个元素比较,按照所需要的顺序选择合适的位置插入。



这样依次类推。

注意:并不是将两个数交换,而是将较大的数后移。例如上图,待排序第一个为5,将5和9比较,小于9,则将9往后移一位,在和6比较,小于6,将6的位置也往后移一位,再将5和4比较,大于,于是就将5插入到4和6中间的位置。

1.2代码
 //插入排序
    public static void insertSort(int[] arr){
        int bound = 1;
        //[0,bound)是已排序区间
        //[bound,length)待排序区间
        for(;bound < arr.length;bound++){
            int num =  arr[bound];
            int i = bound - 1;

            for(;i >= 0;i--){
                if(num < arr[i]){
                    //说明num应该插入到arr[i]之前,于是就把i的位置往后搬运一位
                    arr[i + 1] = arr[i];
                }else {
                    //说明已经找到合适的位置 了,可以结束循环了
                    break;
                }
            }
            arr[i + 1] = num;
        }
    }
1.3复杂度

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

1.4.特点:

(1)如果数组长度比较短,排序效率很高
(2)如果数组相对有序,那么排序效率也很高
(稳定排序)


2.希尔排序

(针对插入排序进一步改进)

2.1思路


(图源自浏览器)

  • 针对序列进行分组,针对每一个分组分别进行插入排序
  • 随之调整分组的变化,逐渐使整个数组逼近有序的状态
    (常见的序列选择:size/2,size/4,size/8……直到1(也叫希尔序列))


可以看到,此时相比之前已经相对有序多了,在gap = 1,也就是插入排序最终可得有序的状态:

2.2代码
//希尔排序
    public static void shellSort(int[] arr){
        //指定gap序列:
        int gap = arr.length/2;
        while (gap >= 1){
            //构造辅助函数来帮助排序
            _shellSort(arr,gap);
            gap = gap/2;
        }
    }

    private static void _shellSort(int[] arr,int gap) {
        //进行分组插排,分成gap组,同组的相邻元素的下标差值为gap
        //和插入排序是一样的(如果gap = 1,就完全一样)
        int bound = gap;
        for(;bound < arr.length;bound++){
            int num = arr[bound];
            int cur = bound - gap;//同组的相邻元素的下标差值为gap,所以减gap
            
            //同插入排序
            for(;cur >= 0; cur-=gap){
                if(arr[bound] < arr[cur]){
                    arr[cur + gap] =arr[cur];
                }else{
                    break;
                }
            }
            arr[cur + gap] = num;
        }
    }
2.3复杂度

时间复杂度:O(N ^ 2);
空间复杂度:O(1);
(不稳定排序)

2.4特点

希尔排序就是利用了插入排序的两个特点,将长队列划分成短的队列,分别使他们有序来提升效率
(实际上用处不太大)


3.选择排序 3.1思路

遍历待排序区间,将第一个元素和后面的所有元素进行对比,顺序不对则交换这两个元素。第一轮遍历完成后,再从第二个元素开始和后面的进行对比。以此类推。

此时,第一轮遍历结束,第一个元素已排好序,接下来排第二个元素

依次类推,最终排序成功

3.2代码
//选择排序
    public static void selectSort(int[] arr){
        for(int i = 0;i < arr.length - 1;i++){
            for(int j = i + 1;j < arr.length;j++){//首先和该元素后面的那个数对比,所以是i+1
            //如果顺序不对就交换
                if(arr[i] > arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
3.3复杂度

时间复杂度:O(N ^ 2);
空间复杂度:O(1)
(不稳定排序)


4.堆排序

(本质上是优化的选择排序)

4.1思路

(待补充)

4.2代码
 //堆排序
    public static void heapSort(int[] arr){
        //1.先建立堆
        creatHeap(arr);
        //2.需要循环取出堆顶元素,和最后一个元素交换并删除,再从0位置进行调整
        int heapSize = arr.length;//堆的大小
        for(int i = 0;i < arr.length; i++){
            //交换0号元素和堆的最后一个元素
            swap(arr,0,heapSize - 1);
            //把最后一个元素从堆上删除
            heapSize--;
            //从0号位置开始往下进行调整
            shiftDown(arr,heapSize,0);
        }
    }


    private static void creatHeap(int[] arr) {
        for (int i = (arr.length - 1 - 1) / 2; i >= 0 ; i--) {
            shiftDown(arr,arr.length,i);
        }

    }

    private static void swap(int[] arr, int x, int y) {
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }

    private static void shiftDown(int[] arr, int size, int index) {
        int parent = index;
        int child = 2 *parent + 1;
        while (child < size){
            //先找出左右子树比较大的
            if(child + 1 < size && arr[child + 1] > arr[child]){
                child = child + 1;
            }
            //在比较child和parent
            if(arr[child] > arr[parent]){
                swap(arr,parent,child);
            }else{

                break;
            }
            parent = child;
            child = 2 *parent + 1;
        }
    }
4.3复杂度

时间复杂度:O(n * log(n))
空间复杂度:O(1)
(不稳定排序)


5.冒泡排序 5.1思路

(以升序为例)比较两个相邻元素,不符合顺序要求就交换,这样一趟下来就能让最小的元素走到数组的最前(从后往前排)(从前往后排:让最大的元素走到数组的最后)并且就将数组分为已排序区间和待排序区间


5.2代码
//冒泡排序(这个代码是从后往前排,从前往后排原理一样)
    public static void bubbleSort(int[] arr){
        //bound用来区分两个区间
        //第一趟结束后,第一个元素就是最小的元素 ,就位于已排序区间,下面的排序就排序到已排序区间的后面
        for(int bound = 0;bound < arr.length;bound++){
            for(int cur = arr.length - 1; cur > bound ; cur --){
                if(arr[cur - 1] > arr[cur]){
                    int tmp = arr[cur - 1];
                    arr[cur - 1] =  arr[cur];
                    arr[cur] = tmp;
                }
            }
        }
5.3复杂度

时间复杂度:O(N ^ 2);
空间复杂度:O(1);
稳定排序


6.快速排序 6.1思路
  1. 从待排序区间选择一个数,作为基准值(pivot);
  2. Partition: 遍历整个待排序区间,将比基准值小的(可以包含相等的)放到基准值的左边,将比基
    准值大的(可以包含相等的)放到基准值的右边;
  3. 采用分治思想,对左右两个小区间按照同样的方式处理,直到小区间的长度 == 1,代表已经有序,
    或者小区间的长度 == 0,代表没有数据
6.2代码
//快速排序
    public static void quickSort(int[] arr){
        //创建辅助递归的方法,这个方法的参数中,明确指定针对哪个区间进行递归[0,length - 1]
        _quickSort(arr,0,arr.length - 1);
    }

    public static void _quickSort(int[] arr, int left, int right) {
        if(left >= right){
            //如果当前的区间为空,或者只有一个元素,都不需要进行任何处理
            return;
        }

        //针对[left,right]区间进行partition操作,方法的返回值,表示整理完当前区间后,基准值所在的位置
        //遍历过程中的left和right重合的位置
        int index = partition(arr,left,right);

        //递归的对左侧区间进行快速排序
        _quickSort(arr,left,index- 1);

        //递归的对右侧区间进行快速排序
        _quickSort(arr,index+1,right);
    }

    public static int partition(int[] arr, int left, int right) {
        //选取最右侧元素作为基准值,
        int v = arr[right];

        int l = left;
        int r = right;
        //如果l和r重合,说明遍历完成
        while (l < r){
            //先从左往右,找一个比基准值大的数字
            while (l < r && arr[l] <= v){
                l++;
            }
            //再从右往左找一个比基准值小的数字
            while (l < r && arr[r] >= v){
                r--;
            }
            //找到后 将他两交换
            int tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;
        }
        //当l和r重合的时候,就把重合位置的元素和基准值位置进行交换
        int tmp = arr[l];
        arr[l] = arr[right];
        arr[right] = tmp;

        //返回基准值位置
        return l;
    }
6.3复杂度

时间复杂度:O(NlogN)(平均)
空间复杂度:O(logN)(平均)
不稳定排序


7.归并排序 7.1思路

(代补充)

7.2代码
//归并排序
    public static void mergeSort(int[] arr){
        _mergeSort(arr,0,arr.length);


    }

    public static void _mergeSort(int[] arr, int left, int right) {
        if(right - left <= 1){
            //判定当前区间是不是只右一个元素或者没有元素,此时不需要排序
            return;
        }
        int mid = (left  + right)/2;
        //先让[left,right)区间变成有序
        _mergeSort(arr,left,mid);
        //再让[mid,right区间变成有序)
        _mergeSort(arr, mid, right);
        //合并两个有序区间
        merge(arr,left,mid,right);
    }

    //归并排序中的关键操作,就是归并两个有序数组
    //使用该merge方法来完成数组归并的过程
   // 此处两个数组就通过参数的left,mid,right描述
    //[left,mid)左侧数组,[mid,right)右侧数组
    public static void merge(int[] arr,int left,int mid,int right){
        //具体的归并操作,需要创建一个临时的空间来保存归并的结果
        //临时的空间得能保存的下带归并的两个数组 也就是right - left这么长
        int[] tmp = new int[right - left];
        int tmpIndex = 0;//表示当前元素该放到临时空间的哪个位置上
        int cur1 = left;
        int cur2 = mid;
        while (cur1 < mid && cur2 < right){
            if(arr[cur1] <= arr[cur2]){
                //把cur1对应的元素插入到临时空间中
                tmp[tmpIndex] = arr[cur1];
                tmpIndex++;
                cur1++;
            }else {
                //把cur2对应的元素插入到临时空间中
                tmp[tmpIndex] = arr[cur2];
                tmpIndex++;
                cur2++;
            }
        }
        //循环结束后,需要把剩余的元素也都拷贝到最终结果里
        while(cur1 < mid){
            tmp[tmpIndex] = arr[cur1];
            tmpIndex++;
            cur1++;
        }
        while(cur2 < mid){
            tmp[tmpIndex] = arr[cur2];
            tmpIndex++;
            cur2++;
        }
        //把tmp的结果再放回arr数组(原地排序){
        for(int i = 0;i < tmp.length;i++){
            arr[left + i] = tmp[i];
        }
    }
7.3复杂度

时间复杂度:O(N * log(N));
空间复杂度:O(N);
稳定排序

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/937702.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号