常见排序算法(插入排序,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,计数排序,基数排序,桶排序)

本文主要是介绍常见排序算法(插入排序,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,计数排序,基数排序,桶排序),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一.排序的概念

1.排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作

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

3.内部排序:数据元素全部放在内存中的排序

4.外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序

二.常见的排序

接下来我们将一一讲解上述排序算法的实现

三.常见排序算法的实现

1.直接插入排序

1.1基本思想

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。实际中我们玩扑克牌时,就用了插入排序的思想

1.2实现

    /*** 时间复杂度:O(N^2)*      最好情况下呢? 有序的时候  O(n)*      结论:对于直接插入排序来说  数据越有序 越快* 空间复杂度:O(1)* 稳定性:稳定*     一个稳定的排序  可以实现为不稳定的排序*     但是 一个本身就不稳定的排序  无法实现为稳定的排序** 场景:当前有一组数据 基本上趋于有序 那么就可以使用直接插入排序* 优点:越有序越快* @param array*/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--){//将tmp与下标为0到i-1的作比较,若tmp大则将tmp赋给该下标后一位if(array[j]>tmp){array[j+1]=array[j];}else{break;}}array[j+1]=tmp;}}

2希尔排序

2.1基本思想

希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成多个组,所有距离为gap的记录分在同一组内,并对每一组内的记录进行排序。然后,取重复上述分组和排序的工作。当到达gap=1时,所有记录在统一组内排好序。

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的希尔排序的时间复杂度都不固定

2.2实现

    /*** 稳定性:不稳定* 时间复杂度:logN* @param array*/public static void shellSort(int[] array){int gap=array.length;while(gap>1){gap=gap/3+1;shell(array,gap);}}public 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++){if(array[j]>tmp){array[j+gap]=array[j];}else{break;}}array[j+gap]=tmp;}}

3选择排序

3.1基本思想

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完

3.2实现

    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)* 稳定性:不稳定的排序* @param array*/public static void selectSort1(int[] array){for(int i=0;i< array.length;i++){int minIndex=i;for(int j=i+1;j< array.length;j++){if(array[j]<array[minIndex]){minIndex=j;}}swap(array,minIndex,i);}}public static void selectSort(int[] array){int left=0;int right=array.length-1;while(left<right){int minIndex=left;int maxIndex=left;for(int i=left+1;i<=right;i++){if(array[i]<array[minIndex]){minIndex=i;}if(array[i]>array[maxIndex]){maxIndex=i;}}swap(array,minIndex,left);//如果最大值是left下标,那么上面交换完成以后,//最大值跑到了最小值的位置,所以要更新最大值下标if(maxIndex==left){maxIndex=minIndex;}swap(array,maxIndex,right);left++;right--;}}

4堆排序

4.1基本思想

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆

4.2实现

 public static void createBigHeap(int[] array){for (int parent=(array.length-1-1/)/2;parent>=0;parent--){siftDown(parent,array,array.length);}}private static void siftDown(int parent,int[] array,int end){int child=2*parent+1;while(child<end){if(child+1<end&&array[child]<array[child+1]){child++;}if(array[child]>array[parent]){swap(array,child,parent);parent=child;child=parent*2+1;}else{break;}}}/*** 时间复杂度:O(N*logN)* 空间复杂度:O(1)* 稳定性:不稳定* @param array*/public static void heapSort(int[] array){createBigHeap(array);int end=array.length-1;while(end>=0){swap(array,0,end);siftDown(0,array,end);end--;}}

5冒泡排序

5.1基本思想

根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置

5.2实现

/*** 时间复杂度:不管数据有序与否,不优化的情况下均为O(N^2)* 空间复杂度:1* 稳定性:稳定** @param array*/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-i-1;j++){if(array[j]>array[j+1]){swap(array,j,j+1);flg=true;}}if(!flg){//优化下,当数据有序,时间复杂度为O(N)break;}}}

6快速排序

6.1基本思想

任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止

6.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) {insertSortRange(array, start, end);return;}int index = midThreeNum(array, start, end);swap(array, index, start);int par = partition(array, start, end);quick(array, start, par - 1);quick(array, par + 1, end);}public static void insertSortRange(int[] array, int left, int right) {for (int i = left + 1; i <= right; i++) {int tmp = array[i];int j = i - 1;for (; j >= left; j--) {if (array[j] > tmp) {array[j + 1] = array[j];} else {break;}}array[j + 1] = tmp;}}//返回值是中位数的下标private static int midThreeNum(int[] array, int left, int right) {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 partitionHoare(int[] array, int left, int right) {int i = left;int tmp = array[left];while (left < right) {while (left < right && array[right] >= tmp) {right--;}while (left < right && array[left] <= tmp) {left++;}swap(array, left, right);}swap(array, left, i);return left;}private static int partition(int[] array, int left, int right) {int tmp = array[left];while (left < right) {while (left < right && array[right] >= tmp) {right--;}array[left] = array[right];while (left < right && array[left] <= tmp) {left++;}array[right] = array[left];}array[left] = tmp;return left;}private static int partitionPre(int[] array, int left, int right) {int prev = left;int cur = left + 1;while (cur <= right) {if (array[cur] < array[left] && array[++prev] != array[cur]) {swap(array, cur, prev);}cur++;}swap(array, prev, left);return prev;}public static void quickSortNor(int[] array) {Stack<Integer> stack = new Stack<>();int left = 0;int right = array.length - 1;int par = partition(array, left, right);if (par > left + 1) {stack.push(left);stack.push(par - 1);}if (par < right - 1) {stack.push(par + 1);stack.push(right);}while (!stack.isEmpty()) {right = stack.pop();left = stack.pop();par = partition(array, left, right);if (par > left + 1) {stack.push(left);stack.push(par - 1);}if (par < right - 1) {stack.push(par + 1);stack.push(right);}}}

7归并排序

7.1基本思想

建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并

7.2实现

 public static void mergeSort(int[] array) {mergeSortFun(array, 0, array.length - 1);}public static void mergeSortFun(int[] array, int left, int right) {if (left >= right) {return;}int mid = (right + left) / 2;mergeSortFun(array, left, mid);mergeSortFun(array, mid + 1, right);}private static void merge(int[] array,int left,int mid,int right){int[] tmp=new int[right-left+1];int k=0;int s1=left;int e1=mid;int s2=mid+1;int e2=right;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++];}//走到这里 相当于tmp数组中 所有元素都有序了//接下来将tmp数组的内容拷贝到array数组当中for(int i=0;i<k;i++){array[i+left]=tmp[i];}}/*** 非递归实现归并排序*/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;}}

8其他排序(计数排序、基数排序、桶排序)

8.1计数排序

计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用

操作步骤
1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

/*** 计数排序* 时间复杂度:O(N+范围)* 空间复杂度:O(范围)* 稳定性:稳定*/public static void countSort(int[] array){//1.遍历数组,求最大值与最小值int maxVal=array[0];int minVal=array[0];for(int i=0;i<array.length;i++){if(maxVal<array[i]){maxVal=array[i];}if(minVal>array[i]){minVal=array[i];}}//2.定义count数组int[] count=new int[maxVal-minVal+1];//3.遍历array数组,把值放入计数数组中for(int i=0;i<array.length;i++){int val=array[i];count[val-minVal]++;}//4.以上3步完成之后,计数数组已经存好了相应的数据//接下来 开始遍历数组 计数数组int index=0;for(int i=0;i<count.length;i++){while(count[i]>0){array[index]=i+minVal;index++;count[i]--;}}}

 

8.2基数排序

1.10 基数排序 | 菜鸟教程 (runoob.com)

8.3桶排序

1.9 桶排序 | 菜鸟教程 (runoob.com)


如果上述内容对您有帮助,希望给个三连谢谢! 

 

这篇关于常见排序算法(插入排序,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,计数排序,基数排序,桶排序)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/923959

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

如何选择适合孤独症兄妹的学校?

在探索适合孤独症儿童教育的道路上,每一位家长都面临着前所未有的挑战与抉择。当这份责任落在拥有孤独症兄妹的家庭肩上时,选择一所能够同时满足两个孩子特殊需求的学校,更显得尤为关键。本文将探讨如何为这样的家庭做出明智的选择,并介绍星贝育园自闭症儿童寄宿制学校作为一个值得考虑的选项。 理解孤独症儿童的独特性 孤独症,这一复杂的神经发育障碍,影响着儿童的社交互动、沟通能力以及行为模式。对于拥有孤独症兄

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO