几大常用的排序算法

这篇具有很好参考价值的文章主要介绍了几大常用的排序算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


一、插入排序

直接插入排序是一种简单的插入排序法,其基本思想是:
在待排序的元素中,假设第一个元素已有序,现将后面的元素与第一个元素作比较,比第一个元素小插入到前面已经排好的序列中,使得前面的元素有序。按照此法对所有元素进行插入,直到整个序列有序为止
动图演示:
几大常用的排序算法,排序算法,算法,数据结构
代码如下所示:

    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                //加不加等号 能取决于这个排序的稳定性
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }
       时间复杂度:
                最坏情况下:O(N^2)
                最好情况下:O(N)
       空间复杂度:O(1)
       稳定性:稳定的排序

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

二、希尔排序(缩小增量排序)

希尔排序法又称缩小增量排序。希尔排序的基本步骤是:
1.先选定一个小于N的整数gap作为第一增量,然后将所有距离为gap的元素分在同一组,并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量,重复上述操作…
2.当增量的大小减到1时,就相当于整个序列被分到一组,进行一次直接插入排序,排序完成
动图演示:
几大常用的排序算法,排序算法,算法,数据结构
先将待排序列进行预排序,使待排序列接近有序,然后再对该序列进行一次插入排序
代码如下:

    public static void shellSort(int[] array) {
        int gap = array.length;
        //进行预排序
        while (gap > 1) {
            gap = gap / 2;
            //对每一组进行插入排序
            shell(array,gap);
        }
    }
    private static void shell(int[] array,int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j-=gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在很多书中给出的希尔排序的时间复杂度都不固定

          稳定性:是一个不稳定的排序

三、选择排序

每次从待排序列中选出一个最小值,然后放在序列的起始位置,直到全部待排数据排完即可
动图演示:
几大常用的排序算法,排序算法,算法,数据结构
代码如下所示:

    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            //最小值
            int minIndex = i;
            int j = i + 1;
            for (; j < array.length; j++) {
                if(array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
         swap(array, i, minIndex);
        }
    }
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
      时间复杂度:O(N^2)
      空间复杂度:O(1)
      稳定性:不稳定

四、堆排序

堆排序可以看之前的这篇博客【数据结构】之优先级队列(堆)

      时间复杂度:O(n*logN)
      空间复杂度:O(1)
      稳定性:不稳定

五、冒泡排序

左右两个相邻元素进行比较并交换
动图演示:
几大常用的排序算法,排序算法,算法,数据结构
代码如下所示:

    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    flg = true;
                }
            }
            if(flg == false) {
                return;
            }
        }
    }
      时间复杂度:最好和最坏情况下都是O(N^2)
      空间复杂度:O(1)
      稳定性:稳定

六、快速排序

6.1 Hoare法

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

    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }
    private static void quick(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }
        int pivot = partitionHoare(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    private static int partitionHoare(int[] array,int left,int right) {
        int tmp = array[left];//基准
        int i = left;
        while (left < right) {
            //第一个判断防止数组越界,第二个是从右边找比基准小的
            while (left < right && array[right] >= tmp) {
                right--;
            }
            //第一个也是防止数组出现越界,第二个是从左边找比基准大的
            while (left < right && array[left] <= tmp) {
                left++;
            }
            //左边大的和右边小的进行交换
            swap(array,left,right);
        }
        //将相遇点和基准进行交换
        swap(array,i,left);
        return left;
    }

6.2挖坑法

思路:
挖坑法和Hoare法的思路类似
1.选出一个数据(一般是最左边或是最右边的)存放在key变量中,在该数据位置形成一个坑
2、定义一个left和一个right,left从左向右走,right从右向左走。(若在最左边挖坑,则需要right先走;若在最右边挖坑,则需要left先走)
后面的过程就和Hoare法类型
动图演示:
几大常用的排序算法,排序算法,算法,数据结构
代码如下所示:

    private static int partition(int[] array,int left,int right) {
        int tmp = array[left];
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            if(left >= right) {
                break;
            }
            array[left] = array[right];
            while (left < right && array[left] <= tmp) {
                left++;
            }
            if(left >= right) {
                break;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }

快排的优化

1.三数取中法找中间大数字的下标
2.递归到某个小的区间时使用插入排序
整体代码:

    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }
    private static void quick(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }
        if(end-start+1 <= 10) {
            insertSort2(array, start, end);
            return;
        }
        //三数取中  index是中间大的数字 的 下标
        int index = middleNum(array,start,end);
        swap(array,index,start);
        
        int pivot = partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    private static void insertSort2(int[] array,int start,int end) {
        for (int i = start+1; i <= end; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= start ; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    private static int middleNum(int[] array,int left,int right) {
        int mid = left+((right-left) >> 1);
        //int mid = (left+right)/2;
        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid] < array[right]) {
                return right;
            }else if(array[mid] > array[left]) {
                return left;
            }else {
                return mid;
            }
        }
    }
    private static int partition(int[] array,int left,int right) {
        int tmp = array[left];
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            if(left >= right) {
                break;
            }
            array[left] = array[right];
            while (left < right && array[left] <= tmp) {
                left++;
            }
            if(left >= right) {
                break;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }
      时间复杂度: 
               最坏情况下:O(N^2)
               最好情况下:O(N*logN)
               
      空间复杂度:
               最坏情况下:O(N)
               最好情况下:O(logN)           
      稳定性:不稳定                  

快排的非递归实现

这里我们使用栈来实现非递归的快排

	public static void quickSortNor(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        //找基准
        int pivot = partition(array,left,right);
        //基准左边的区间大于left进行入栈
        if(pivot-1 > left) {
            stack.push(left);
            stack.push(pivot-1);
        }
        //基准右边的区间小于right进行入栈
        if(pivot+1 < right) {
            stack.push(pivot+1);
            stack.push(right);
        }
        //判断栈是否为空 
        //不为空出两个下标再对左和右两个下边进行找基准操作重复以上操作直至数组有序为止
        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = partition(array,left,right);
            if(pivot-1 > left) {
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot+1 < right) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }

七、归并排序

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并
动图演示:
几大常用的排序算法,排序算法,算法,数据结构
代码如下所示:

    public static void mergeSort(int[] array) {
        mergeFunc(array,0,array.length-1);
    }
    private static void mergeFunc(int[] array,int left,int right) {
        if(left >= right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        mergeFunc(array,left,mid);
        mergeFunc(array,mid+1,right);
        //左边和右边分解完进行合并
        merge(array,left,mid,right);
    }
    private static void merge(int[] array,int left,int mid,int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        int[] tmp = new int[right - left + 1];
        int k = 0;
        //确保两个数组都有元素
        while (s1 <= e1 && s2 <= e2) {
            if(array[s1] < array[s2]) {
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }
        //看两个数组中 还有哪个有数据
        while (s1 <= e1) {
            tmp[k++] = array[s1++];
        }
        while (s2 <= e2) {
            tmp[k++] = array[s2++];
        }
        //拷贝回原来的数组
        for (int i = 0; i < k; i++) {
            array[i+left] = tmp[i];
        }
    }
    时间复杂度:O(n*logN)
    空间复杂度:O(N)
    稳定性:稳定

归并的非递归实现

    public static void mergeSortNor(int[] array) {
        int gap = 1;
        while (gap < array.length) {
            for (int i = 0; i < array.length; i=i+2*gap) {
                int left = i;
                int mid = left + gap - 1;
                if(mid >= array.length) {
                    mid = array.length-1;
                }
                int right = mid + gap;
                if(right >= array.length) {
                    right = array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap *= 2;
        }
    }

八、计数排序

1.统计相同元素出现次数根据
2.统计的结果将序列回收到原来的序列中
3.计数排序只适用于范围集中且重复数据较高的数据
动图演示:
几大常用的排序算法,排序算法,算法,数据结构
代码如下所示:

    public static void countSort(int[] array) {
        int min = array[0];
        int max = array[0];
        //找到最大值和最小值
        for (int i = 0; i < array.length; i++) {
            if(min > array[i]) {
                min = array[i];
            }
            if(max < array[i]) {
                max = array[i];
            }
        }
        //创建一个计数数组
        int[] count = new int[max-min+1];
        for (int i = 0; i < array.length; i++) {
            int index = array[i]-min;
            count[index]++;
        }
        //遍历这个计数数组
        int k = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] !=0) {
                array[k] = i+min;
                k++;
                count[i]--;
            }
        }
    }
    时间复杂度:O(范围+n)
    范围 = max-min
    空间复杂度:O(范围)
    稳定性:稳定

在以上几种排序中属于稳定排序的只有:插入排序、冒泡排序、归并排序、计数排序文章来源地址https://www.toymoban.com/news/detail-840799.html

到了这里,关于几大常用的排序算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构——排序算法——归并排序

    在第二个列表向第一个列表逐个插入的过程中,由于第二个列表已经有序,所以后续插入的元素一定不会在前面插入的元素之前。在逐个插入的过程中,每次插入时,只需要从上次插入的位置开始,继续向后寻找插入位置即可。这样一来,我们最多只需要将两个有序数组遍历

    2024年02月09日
    浏览(47)
  • 【排序算法】数据结构排序详解

    前言: 今天我们将讲解我们数据结构初阶的最后一部分知识的学习,也是最为“炸裂”的知识---------排序算法的讲解!!!! 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列中,

    2023年04月08日
    浏览(50)
  • 数据结构和算法笔记4:排序算法-归并排序

    归并排序算法完全遵循分治模式。直观上其操作如下: 分解:分解待排序的n个元素的序列成各具n/2个元素的两个子序列。 解决:使用归并排序递归地排序两个子序列。 合并:合并两个已排序的子序列以产生已排序的答案。 我们直接来看例子理解算法的过程,下面是要排序

    2024年01月21日
    浏览(64)
  • 【数据结构与算法】十大经典排序算法-希尔排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 希尔排序是一种插入排序的改进版本,旨在解决插入排序在处理大规模数据时的效率问题。通过将数组分为多个子序列并对

    2024年02月12日
    浏览(80)
  • 【数据结构与算法】十大经典排序算法-快速排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 快速排序(Quick Sort)是一种高效的排序算法,是对冒泡排序的优化。它采用分治法(Divide and Conquer)的思想,将待排序序列

    2024年02月13日
    浏览(65)
  • 【数据结构与算法】十大经典排序算法-冒泡排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌴 掘金 :HelloCode 🌞 知乎 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 冒泡排序(Bubble Sort)是一种简单的排序算法,它通过重复地交换相邻元素的位置来将最大(或最小)的元素逐步“冒泡”到

    2024年02月14日
    浏览(75)
  • 【数据结构与算法】十大经典排序算法-插入排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 插入排序(Insertion Sort)是一种简单直观的排序算法,其基本思想是将一个记录插入到已排好序的有序序列中,直到所有记录

    2024年02月13日
    浏览(83)
  • 数据结构——排序算法之快速排序

        个人主页: 日刷百题 系列专栏 : 〖C/C++小游戏〗 〖Linux〗 〖数据结构〗   〖C语言〗 🌎 欢迎各位 → 点赞 👍+ 收藏 ⭐️+ 留言 📝  ​ ​ 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。 基本思想: 任取待排序元素序列中 的某元素作为基准值,按照

    2024年01月21日
    浏览(60)
  • 【数据结构与算法】排序算法(选择排序,冒泡排序,插入排序,希尔排序)

    基本概念这了就不浪费时间解释了,这四种都是很简单的排序方式,本专栏后续文章会出归并排序,计数排序,快速排序,堆排序,桶排序等排序算法,今天这篇文章中给出选择排序,冒泡排序,插入排序和希尔排序的实现; 如果发现文章中有错误,还请大家指出来,我会非

    2024年02月15日
    浏览(86)
  • 数据结构与算法-排序算法

    递归将整个函数的调用过程 调用过程 如何在CSDN博客中插入公式和各种符号 类似二叉树的后续遍历 递归行为和递归行为时间复杂度的估算 master 公式 : T ( n ) = a × T ( n b ) + O ( n d ) T(n) = a times T (frac{n}{b}) + O(n^d) T ( n ) = a × T ( b n ​ ) + O ( n d ) T ( n ) T(n) T ( n ) : 母问题的规模

    2024年02月15日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包