您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

十大经典排序算法(java实现、配图解,附源码)

时间:2022-03-04 10:14:18  来源:博客园  作者:IT界彭于晏

前言:

本文章主要是讲解我个人在学习JAVA开发环境的排序算法时做的一些准备,以及个人的心得体会,汇集成本篇文章,作为自己对排序算法理解的总结与笔记。

内容主要是关于十大经典排序算法的简介、原理、动静态图解和源码实现的分析。

对于一名程序员来讲,我们都知道数据结构与算法起初是用于C语言居多,然而在Java语言下使用算法的案例却很少,因此,特别整理了在Java开发环境的排序算法,供大家一起学习探讨。

一、排序算法

1.排序算法概述(百度百科):

所谓排序算法,即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。这种新序列遵循着一定的规则,体现出一定的规律,因此,经处理后的数据便于筛选和计算,大大提高了计算效率。对于排序,我们首先要求其具有一定的稳定性,即当两个相同的元素同时出现于某个序列之中,则经过一定的排序算法之后,两者在排序前后的相对位置不发生变化。换言之,即便是两个完全相同的元素,它们在排序过程中也是各有区别的,不允许混淆不清。

2.《数据结构与算法》中的排序算法

常见的排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

算法图解(菜鸟教程借图):

十大经典排序算法(java实现、配图解,附源码)

 

图解分析:

十大经典排序算法(java实现、配图解,附源码)

 

3.算法分析

时间复杂度

平方阶 (O(n2)) 排序 各类简单排序:直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序;

O(n1+§)) 排序,§ 是介于 0 和 1 之间的常数。 希尔排序

线性阶 (O(n)) 排序 基数排序,此外还有桶、箱排序。

关于稳定性

稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。

名词解释:

  • n:数据规模
  • k:"桶"的个数
  • In-place:占用常数内存,不占用额外内存
  • Out-place:占用额外内存
  • 稳定性:排序后 2 个相等键值的顺序和排序之前它们的顺序相同
  1. 平均时间复杂度是指所有可能的输入实例均以等概率的出现情况下得到算法的运行时间
  2. 最坏时间复杂度,一般讨论的时间复杂度均是最坏情况下的时间复杂度,这样做的原因是最坏情况下的时间复杂度是算法在任何输入实例上运行的界限,这就保证了算法的运行时间不会比最坏情况更长。
  3. 平均时间复杂度和最坏时间复杂度是否一样,这就需要根据算法不同而不同了。

二、十大经典排序算法(Java开发版)

PS:案例均以数组{15,63,97,12,235,66}排序为例

1.冒泡排序

冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

1.1实现原理

  • 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  • 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  • 针对所有的元素重复以上的步骤,除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
十大经典排序算法(java实现、配图解,附源码)

 

1.2动图演示

十大经典排序算法(java实现、配图解,附源码)

 

1.3实例展示

十大经典排序算法(java实现、配图解,附源码)

 

 1 import java.util.Arrays;
 2 public class BubbleSort {
 3     public static void mAIn(String[] args) {
 4         int[] arrays =new int[]{15,63,97,12,235,66};
 5         for (int i=0;i<arrays.length-1;i++){
 6             
 7 //            控制比较次数,三者交换,实现排序
 8             for(int j=0;j<arrays.length-1-i;j++){
 9                 if (arrays[j] > arrays[j+1]){
10                     int temp = 0;//类似空桶
11                     temp = arrays[j]; //A桶中水倒入空桶C中
12                     arrays[j] = arrays[j+1];//把B桶的水倒入A桶中
13                     arrays[j+1] = temp;//把C桶的水倒入B桶中
14                 }
15             }
16         }
17         System.out.println(Arrays.toString(arrays));
18     }
19 }
十大经典排序算法(java实现、配图解,附源码)

 

排序结果展示:

十大经典排序算法(java实现、配图解,附源码)

 

2.快速排序

快速排序(Quicksort),计算机科学词汇,适用领域Pascal,c++等语言,是对冒泡排序算法的一种改进。

2.1实现原理

快速排序是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分所有的数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

十大经典排序算法(java实现、配图解,附源码)

 

2.2 动图演示

十大经典排序算法(java实现、配图解,附源码)

 

2.3实例展示

十大经典排序算法(java实现、配图解,附源码)

 

 1 import java.util.Arrays;
 2 public class QuickSort {
 3     public static void main(String[] args) {
 4         int[] arrays = new int[]{15,63,97,12,235,66};
 5         sort(arrays,0,arrays.length-1);
 6         System.out.println(Arrays.toString(arrays));
 7     }
 8     public static void sort(int[] arrays,int left,int right){
 9         int l  = left;
10         int r = right;
11 
12         int pivot = arrays[(left+right)/2];
13         int temp = 0;
14         while (l<r){
15 
16             //在左边查找小于中间值的
17             while(arrays[l]<pivot){
18                 l++;
19             }
20             //查询右边小于中间值
21             while (arrays[r]>pivot){
22                 r--;
23             }
24             if (l>=r){
25                 break;
26             }
27             temp = arrays[l];
28             arrays[l] = arrays[r];
29             arrays[r] = temp;
30 
31 //            交换完数据arrays[l] = pivot
32             if (arrays[l]==pivot){
33                 r--;
34             }
35             if (arrays[r]==pivot){
36                 l++;
37             }
38             if (r==l){
39                 l++;
40                 r--;
41             }
42             if (left<r){
43                 sort(arrays,left,r);
44             }
45             if (right>l){
46                 sort(arrays,l,right);
47             }
48         }
49     }
50 }
十大经典排序算法(java实现、配图解,附源码)

 

排序结果展示:

十大经典排序算法(java实现、配图解,附源码)

 

3.基数排序

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

基数排序是1887年赫尔曼、何乐礼发明的。思想是讲整数按位数切割成不同的数字,然后按每个位数分别比较。

3.1实现原理

讲所有的待比较数值统一设置为同样的数位长度,位数比较短的数前面补零,然后从最地位开始依次进行一次排序,这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

十大经典排序算法(java实现、配图解,附源码)

 

3.2 动图演示

十大经典排序算法(java实现、配图解,附源码)

 

3.3实例展示

十大经典排序算法(java实现、配图解,附源码)

 

  1 import java.text.SimpleDateFormat;
  2 import java.util.Arrays;
  3 import java.util.Date;
  4 
  5 public class BasicSort {
  6 
  7     public static void main(String[] args) {
  8         int[] arrays = new int[]{15,63,97,12,235,66};
  9         SimpleDateFormat simpleDateFormat  =new SimpleDateFormat("yyyy-mm-dd HH:MM:ss:SS");
 10         System.out.println("开始排序前:"+simpleDateFormat.format(new Date()));
 11         sort(arrays);
 12         System.out.println("排序结束:"+simpleDateFormat.format(new Date()));
 13     }
 14 
 15 //     1.获取原序列的最大位多少
 16 //      @param arrays
 17     public static void sort(int[] arrays){
 18 
 19 //        获取最大位数
 20         int max = 0;
 21         for(int i=0;i<arrays.length;i++){
 22             if (arrays[i]>max){
 23                 max = arrays[i];
 24             }
 25         }
 26 
 27 //        获取字符串长度,所以把int类型转字符串类型
 28         int maxLength = (max+"").length();
 29 
 30 //      定义二维数组,大小10,表示10个桶,每一个桶则是一个数组
 31 //       [[],[],[],[],[]...]
 32         int[][] bucket = new int[10][arrays.length];
 33 
 34 //        辅助数组
 35         int[] bucketElementCount = new int[10];
 36 
 37 //        循环获取无序数列
 38         for (int j=0;j<arrays.length;j++){
 39             int locationElement = arrays[j]%10;
 40 
 41 //            放入桶中
 42             bucket[locationElement][bucketElementCount[locationElement]] = arrays[j] ;
 43             bucketElementCount[locationElement]++;
 44         }
 45 
 46 //        遍历每一个桶,讲元素存放原数组中
 47         int index = 0;
 48         for (int k = 0;k<bucketElementCount.length;k++){
 49             if (bucketElementCount[k] !=0){
 50                 for (int l = 0;l<bucketElementCount[k];l++){
 51                     arrays[index++] = bucket[k][l];
 52                 }
 53             }
 54             bucketElementCount[k] = 0;
 55         }
 56         System.out.println(Arrays.toString(arrays));
 57 
 58 //        第一轮针对个位数进行比较
 59         for (int j = 0;j<arrays.length;j++){
 60             int locationElement = arrays[j]/1%10;
 61 
 62             bucket[locationElement][bucketElementCount[locationElement]] = arrays[j];
 63             bucketElementCount[locationElement]++;
 64         }
 65 
 66 //        取出来按照桶的顺序放回原数组中
 67         int indx = 0;
 68         for (int k = 0;k<bucketElementCount.length;k++){
 69             if (bucketElementCount[k] !=0){
 70                 for (int l=0;l<bucketElementCount[k];l++){
 71                     arrays[indx++] = bucket[k][l];
 72                 }
 73             }
 74             bucketElementCount[k] = 0;
 75         }
 76 
 77 //        判断十位数
 78         for (int j = 0;j<arrays.length;j++){
 79             int locationElement = arrays[j]/10%10;
 80 
 81             bucket[locationElement][bucketElementCount[locationElement]] = arrays[j];
 82             bucketElementCount[locationElement]++;
 83         }
 84 
 85 //        取出来按照桶的顺序放回原数组中
 86         indx = 0;
 87         for (int k = 0;k<bucketElementCount.length;k++){
 88             if (bucketElementCount[k] !=0){
 89                 for (int l=0;l<bucketElementCount[k];l++){
 90                     arrays[indx++] = bucket[k][l];
 91                 }
 92             }
 93             bucketElementCount[k] = 0;
 94         }
 95 
 96 //        获取百位数比较
 97         for (int j = 0;j<arrays.length;j++){
 98             int locationElement = arrays[j]/100%10;
 99 
100             bucket[locationElement][bucketElementCount[locationElement]] = arrays[j];
101             bucketElementCount[locationElement]++;
102         }
103 
104 //        取出来按照桶的顺序放回原数组中
105         indx = 0;
106         for (int k = 0;k<bucketElementCount.length;k++){
107             if (bucketElementCount[k] !=0){
108                 for (int l=0;l<bucketElementCount[k];l++){
109                     arrays[indx++] = bucket[k][l];
110                 }
111             }
112             bucketElementCount[k] = 0;
113         }
114         System.out.println("基数排序后的顺序:"+Arrays.toString(arrays));
115     }
116 }
十大经典排序算法(java实现、配图解,附源码)

 

排序结果展示:

十大经典排序算法(java实现、配图解,附源码)

 

4.插入排序

插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动 。

4.1实现原理

插入排序的工作方式像许多人排序一手扑克牌。开始时,我们的左手为空并且桌子上的牌面向下。然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的,原来这些牌是桌子上牌堆中顶部的牌。

插入排序是指在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入,直到整个序列排为有序的过程,称为插入排序。

十大经典排序算法(java实现、配图解,附源码)

 

排序结果展示:

十大经典排序算法(java实现、配图解,附源码)

 

4.3实例展示

十大经典排序算法(java实现、配图解,附源码)

 

 1 public class InsertSort {
 2     public static void main(String[] args) {
 3         int[] array = new int[]{15,63,97,12,235,66};
 4         //控制拿去每一个元素
 5         for(int i=1;i<array.length;i++){
 6             //比较次数
 7             for (int j=i;j>=1;j--){
 8                 //是否小于前面的元素
 9                 if (array[j]<array[j-1]){
10                     int temp = 0;
11                     temp = array[j];
12                     array[j] = array[j-1];
13                     array[j-1] = temp;
14                 }else {
15                     //continue 与 break
16                     break;
17                 }
18             }
19         }
20         System.out.println("排序后的结果:"+ Arrays.toString(array));
21     }
22 }
十大经典排序算法(java实现、配图解,附源码)

 

排序结果展示:

十大经典排序算法(java实现、配图解,附源码)

 

5.选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

5.1实现原理

第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

十大经典排序算法(java实现、配图解,附源码)

 

5.2 动图演示

十大经典排序算法(java实现、配图解,附源码)

 

5.3实例展示

 1 import java.util.Arrays;
 2 public class SelectSort {
 3     public static void main(String[] args) {
 4         int[] arr = new int[]{15,63,97,12,235,66};
 5         for (int i=0;i<arr.length;i++){
 6 
 7             for (int j=arr.length-1;j>i;j--){
 8 
 9                 if (arr[j]<arr[i]){
10 
11                     int temp = 0;
12                     temp = arr[j];
13                     arr[j] = arr[i];
14                     arr[i] = temp;
15                 }
16             }
17         }
18         System.out.println("选择排序后的结果:"+ Arrays.toString(arr));
19     }
20 }
十大经典排序算法(java实现、配图解,附源码)

 

排序结果展示:

十大经典排序算法(java实现、配图解,附源码)

 

6.希尔排序

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终止。

6.1实现原理

先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2

般的初次取序列的一半为增量,以后每次减半,直到增量为1。

十大经典排序算法(java实现、配图解,附源码)

 


十大经典排序算法(java实现、配图解,附源码)

 


十大经典排序算法(java实现、配图解,附源码)

 

6.2 动图演示

十大经典排序算法(java实现、配图解,附源码)

 

6.3实例展示

 1 import java.util.Arrays;
 2 public class ShellSort {
 3     public static void main(String[] args) {
 4         int[] array = new int[]{15,63,97,12,235,66};
 5 
 6 //        实现增量变化
 7         for (int gap = array.length/2;gap>0;gap/=2){
 8 
 9             for (int i=gap;i<array.length;i++){
10 
11                 for (int j=i-gap;j>=0;j-=gap){
12                     if (array[j]>array[j+gap]){
13                         int temp = 0;
14                         temp = array[j];
15                         array[j] = array[j+gap];
16                         array[j+gap] = temp;
17                     }
18                 }
19             }
20         }
21         System.out.println(Arrays.toString(array));
22     }
23 }
十大经典排序算法(java实现、配图解,附源码)

 


十大经典排序算法(java实现、配图解,附源码)

 

7.归并排序

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

7.1实现原理

  • 第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  • 第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置
  • 第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置重复步骤3直到某一指针超出序列尾将另一序列剩下的所有元素直接复制到合并序列尾
十大经典排序算法(java实现、配图解,附源码)

 

我们需要将两个已经有序的子序列合并成一个有序序列,比如上图最后一次合并,将[2,4,5,6]和[1,3,7,8]已经有序的子序列合并最终序列[1,2,3,4,5,6,7,8]

十大经典排序算法(java实现、配图解,附源码)

 

7.2 动图演示

十大经典排序算法(java实现、配图解,附源码)

 

7.3实例展示

十大经典排序算法(java实现、配图解,附源码)

 

 1 import java.util.Arrays;
 2 public class MSort {
 3     public static void main(String[] args) {
 4         int[] array = new int[]{15,63,97,12,235,66};
 5         //临时数组
 6         int[] temp = new int[array.length];
 7         sort(array,0,array.length-1,temp);
 8         System.out.println(Arrays.toString(array));
 9 
10     }
11     public static void sort(int[] array,int left,int right,int[] temp){
12         if (left<right){
13 
14 //            求出中间值
15             int mid = (left+right)/2;
16 
17 //            向左边分解
18             sort(array,left,mid,temp);
19 //            向右边分解
20             sort(array,mid+1,right,temp);
21 //            合并数据
22             sum(array,left,right,mid,temp);
23         }
24     }
25     /**
26      * 合并元素
27      * @param array
28      * @param left
29      * @param right
30      * @param mid
31      * @param temp
32      */
33     public static void sum(int[] array,int left,int right,int mid,int[] temp){
34         int i = left;
35         int j = mid+1;
36 
37 //        指向临时数组下标
38         int t = 0;
39 
40 //        开始循环比较左右两遍数组元素比较
41         while (i<=mid && j<=right){
42 
43             if (array[i]<=array[j]){
44                 temp[t] = array[i];
45                 t++;
46                 i++;
47             }else {
48                 temp[t] = array[j];
49                 t++;
50                 j++;
51             }
52         }
53 
54 //        把剩余的元素直接存放在临时数组中
55         while(i<=mid){
56             temp[t] = array[i];
57             t++;
58             i++;
59         }
60         while (j<=right){
61             temp[t] = array[j];
62             t++;
63             j++;
64         }
65 
66 //        临时数组中的元素拷贝至原数组中
67         int tempIndex = left;
68         int k = 0;
69         while (tempIndex<=right){
70             array[tempIndex] = temp[k];
71             k++;
72             tempIndex++;
73         }
74     }
75 }
十大经典排序算法(java实现、配图解,附源码)

 

排序结果展示:

十大经典排序算法(java实现、配图解,附源码)

 

8.计数排序

计数排序是一个非基于比较的排序算法,该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法。 当然这是一种牺牲空间换取时间的做法,而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序(基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序,堆排序)

8.1实现原理

假设输入的线性表L的长度为n,L=L1,L2,..,Ln;线性表的元素属于有限偏序集S,|S|=k且k=O(n),S={S1,S2,..Sk};则计数排序可以描述如下:

  1. 扫描整个集合S,对每一个Si∈S,找到在线性表L中小于等于Si的元素的个数T(Si);
  2. 扫描整个线性表L,对L中的每一个元素Li,将Li放在输出线性表的第T(Li)个位置上,并将T(Li)减1。
十大经典排序算法(java实现、配图解,附源码)

 

8.2 动图演示

十大经典排序算法(java实现、配图解,附源码)

 

8.3实例展示

十大经典排序算法(java实现、配图解,附源码)

 

 1 public class CountSort {
 2     public static void main(String[]args){
 3         //排序的数组
 4         int a[]={15,63,97,12,235,66};
 5         int b[]=countSort(a);
 6         for(int i:b){
 7             System.out.print( i+",");
 8         }
 9         System.out.println();
10     }
11     public static int[] countSort(int[]a){
12         int b[] = new int[a.length];
13         int max = a[0],min = a[0];
14         for(int i:a){
15             if(i>max){
16                 max=i;
17             }
18             if(i<min){
19                 min=i;
20             }
21         }//这里k的大小是要排序的数组中,元素大小的极值差+1
22         int k=max-min+1;
23         int c[]=new int[k];
24         for(int i=0;i<a.length;++i){
25             c[a[i]-min]+=1;//优化过的地方,减小了数组c的大小
26         }
27         for(int i=1;i<c.length;++i){
28             c[i]=c[i]+c[i-1];
29         }
30         for(int i=a.length-1;i>=0;--i){
31             b[--c[a[i]-min]]=a[i];//按存取的方式取出c的元素
32         }
33         return b;
34     }
35 }
十大经典排序算法(java实现、配图解,附源码)

 

排序结果展示:

十大经典排序算法(java实现、配图解,附源码)

 


堆排序

堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

9.1实现原理

  1. 创建一个堆 H[0……n-1];
  2. 把堆首(最大值)和堆尾互换;
  3. 把堆的尺寸缩小 1,并调用 shift_down(0),目的是把新的数组顶端数据调整到相应位置;
  4. 重复步骤 2,直到堆的尺寸为 1。
十大经典排序算法(java实现、配图解,附源码)

 

9.2 动图演示

十大经典排序算法(java实现、配图解,附源码)

 

9.3实例展示

十大经典排序算法(java实现、配图解,附源码)

 

 1 public static int[] heapSort(int[] array) {
 2         //这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1
 3         for (int i = array.length / 2 - 1; i >= 0; i--) {  
 4             adjustHeap(array, i, array.length);  //调整堆
 5         }
 6   
 7         // 上述逻辑,建堆结束
 8         // 下面,开始排序逻辑
 9         for (int j = array.length - 1; j > 0; j--) {
10             // 元素交换,作用是去掉大顶堆
11             // 把大顶堆的根元素,放到数组的最后;换句话说,就是每一次的堆调整之后,都会有一个元素到达自己的最终位置
12             swap(array, 0, j);
13             // 元素交换之后,毫无疑问,最后一个元素无需再考虑排序问题了。
14             // 接下来我们需要排序的,就是已经去掉了部分元素的堆了,这也是为什么此方法放在循环里的原因
15             // 而这里,实质上是自上而下,自左向右进行调整的
16             adjustHeap(array, 0, j);
17         }
18         return array;
19     }
20   
21     /**
22     * 整个堆排序最关键的地方
23     * @param array 待组堆
24     * @param i 起始结点
25     * @param length 堆的长度
26     */
27     public static void adjustHeap(int[] array, int i, int length) {
28         // 先把当前元素取出来,因为当前元素可能要一直移动
29         int temp = array[i];
30         for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {  //2*i+1为左子树i的左子树(因为i是从0开始的),2*k+1为k的左子树
31             // 让k先指向子节点中最大的节点
32             if (k + 1 < length && array[k] < array[k + 1]) {  //如果有右子树,并且右子树大于左子树
33                 k++;
34             }
35             //如果发现结点(左右子结点)大于根结点,则进行值的交换
36             if (array[k] > temp) {
37                 swap(array, i, k);
38                 // 如果子节点更换了,那么,以子节点为根的子树会受到影响,所以,循环对子节点所在的树继续进行判断
39                     i  =  k;
40                         } else {  //不用交换,直接终止循环
41                 break;
42             }
43         }
44     }
45   
46     /**
47     * 交换元素
48     * @param arr
49     * @param a 元素的下标
50     * @param b 元素的下标
51     */
52     public static void swap(int[] arr, int a, int b) {
53         int temp = arr[a];
54         arr[a] = arr[b];
55         arr[b] = temp;
56     }
十大经典排序算法(java实现、配图解,附源码)

 

排序结果展示:

十大经典排序算法(java实现、配图解,附源码)

 

10.桶排序

桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。

10.1实现原理

假定:输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数。将区间[0, 1)划分为n个大小相等的子区间(桶),每桶大小1/n:[0, 1/n), [1/n, 2/n), [2/n, 3/n),…,[k/n, (k+1)/n ),…将n个输入元素分配到这些桶中,对桶中元素进行排序,然后依次连接桶输入0 ≤A[1..n] <1辅助数组B[0..n-1]是一指针数组,指向桶(链表)。

十大经典排序算法(java实现、配图解,附源码)

 

10.2 动图演示

十大经典排序算法(java实现、配图解,附源码)

 

然后,元素在每个桶中排序:

十大经典排序算法(java实现、配图解,附源码)

 

排序结果展示:

十大经典排序算法(java实现、配图解,附源码)

 

 1 public static void basket(int data[])//data为待排序数组
 2 {
 3 int n=data.length;
 4 int bask[][]=new int[10][n];
 5 int index[]=new int[10];
 6 int max=Integer.MIN_VALUE;
 7 for(int i=0;i<n;i++)
 8 {
 9 max=max>(Integer.toString(data[i]).length())?max:(Integer.toString(data[i]).length());
10 }
11 String str;
12 for(int i=max-1;i>=0;i--)
13 {
14 for(int j=0;j<n;j++)
15 {
16 str="";
17 if(Integer.toString(data[j]).length()<max)
18 {
19 for(int k=0;k<max-Integer.toString(data[j]).length();k++)
20 str+="0";
21 }
22 str+=Integer.toString(data[j]);
23 bask[str.charAt(i)-'0'][index[str.charAt(i)-'0']++]=data[j];
24 }
25 int pos=0;
26 for(int j=0;j<10;j++)
27 {
28 for(int k=0;k<index[j];k++)
29 {
30 data[pos++]=bask[j][k];
31 }
32 }
33 for(intx=0;x<10;x++)index[x]=0;
34 }
35 }
十大经典排序算法(java实现、配图解,附源码)

 

排序结果展示:

十大经典排序算法(java实现、配图解,附源码)

 

总结:

以上便是本篇文章所写的关于十大经典排序算法所有内容了,码字不易,对你有帮助的话,请给个三连(关注、点赞、收藏)有问题可评论区留言讨论。
原文链接:
https://www.cnblogs.com/zbcxy506/p/zbcxy506_3arithmetic-01.html



Tags:排序算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
我们一起聊聊C#堆排序算法
前言堆排序是一种高效的排序算法,基于二叉堆数据结构实现。它具有稳定性、时间复杂度为O(nlogn)和空间复杂度为O(1)的特点。堆排序实现原理 构建最大堆:将待排序数组构建成一...【详细内容】
2023-10-10  Search: 排序算法  点击:(285)  评论:(0)  加入收藏
面试过程中常见的排序算法问题你见个?附常见排序算法源代码
在面试过程中,排序算法常常是一个重要的考点。排序算法的熟练掌握不仅能展现出候选人对基本数据结构的理解,也能展示出他们的算法设计和问题解决能力。下面我们将详细讨论几种...【详细内容】
2023-10-09  Search: 排序算法  点击:(87)  评论:(0)  加入收藏
目前世界上最快的排序算法-Timsort算法思想原理及C代码实现
排序算法在计算机科学中扮演着重要的角色,影响着各种应用程序的性能和效率。其中,Timsort 算法因其高效的性能和广泛的应用而备受瞩目。在本文中,我们将深入探究 Timsort 算法...【详细内容】
2023-08-05  Search: 排序算法  点击:(286)  评论:(0)  加入收藏
详解 DeepMind 排序算法
作者 | Justine Tunney译者 | 弯月责编 | 夏萌出品 | CSDN(ID:CSDNnews)近日,DeepMind 在博客发表了一篇阐述排序算法内核的论文。他们借鉴了构建 AlphaGo 积累的有关深度学习的...【详细内容】
2023-06-20  Search: 排序算法  点击:(189)  评论:(0)  加入收藏
AlphaDev将排序算法提速70%!C语言库作者一文详解DeepMind最新AI
图片来源:由无界 AI&zwnj; 生成几天前,DeepMind推出了AlphaDev,直接把排序算法提速70%。这一全新AI系统,便是基于下棋高手AlphaGo打造。而这项研究恰恰激起了前谷歌研究人员Just...【详细内容】
2023-06-20  Search: 排序算法  点击:(150)  评论:(0)  加入收藏
AI重写排序算法,速度快70%:DeepMind AlphaDev革新计算基础
计算的基础就此改变了。「通过交换和复制移动,AlphaDev 跳过了一个步骤,以一种看似错误,但实际上是捷径的方式连接项目。」这种前所未见、违反直觉的思想不禁让人回忆起 2016...【详细内容】
2023-06-08  Search: 排序算法  点击:(374)  评论:(0)  加入收藏
Go 语言实现快速排序算法
快速排序是由东尼&middot;霍尔所发明的一种排序算法,时间复杂度是 O(nlogn), 是不稳定排序算法。快速排序使用分治思想,通过一趟排序将要排序的数据分割成独立的两部分,其中一部...【详细内容】
2023-05-08  Search: 排序算法  点击:(358)  评论:(0)  加入收藏
看动图学算法:冒泡排序算法的原理和Java讲解
冒泡算法是一种简单的排序算法,它的基本思想是通过相邻元素之间的比较和交换,将大的元素慢慢地“冒泡”到数组的最后一个位置。冒泡算法在实现上非常简单,但它的时间复杂度较高...【详细内容】
2023-05-06  Search: 排序算法  点击:(369)  评论:(0)  加入收藏
常用的排序算法
排序算法是计算机科学领域中非常重要的基础算法之一,主要应用于数据处理中,将未排序的数据按照一定规则排列,以便后续的计算和数据分析。目前常用的排序算法有多种,包括冒泡排...【详细内容】
2023-04-27  Search: 排序算法  点击:(353)  评论:(0)  加入收藏
简述几种常用的排序算法
本文分享自华为云社区《深入浅出八种排序算法-云社区-华为云》,作者:嵌入式视觉 。归并排序和快速排序是两种稍微复杂的排序算法,它们用的都是分治的思想,代码都通过递归来实现,...【详细内容】
2023-03-27  Search: 排序算法  点击:(154)  评论:(0)  加入收藏
▌简易百科推荐
小红书、视频号、抖音流量算法解析,干货满满,值得一看!
咱们中国现在可不是一般的牛!网上的网友已经破了十个亿啦!到了这个互联网的新时代,谁有更多的人流量,谁就能赢得更多的掌声哦~抖音、小红书、、视频号,是很多品牌必争的流量洼地...【详细内容】
2024-02-23  二手车小胖说    Tags:流量算法   点击:(17)  评论:(0)  加入收藏
雪花算法详解与Java实现:分布式唯一ID生成原理
SnowFlake 算法,是 Twitter 开源的分布式 ID 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。在分布式系统中的应用十分广泛,且 ID 引入了时间戳...【详细内容】
2024-02-03   一安未来  微信公众号  Tags:雪花算法   点击:(53)  评论:(0)  加入收藏
程序开发中常用的十种算法,你用过几种?
当编写程序时,了解和使用不同的算法对解决问题至关重要。以下是C#中常用的10种算法,每个算法都伴随着示例代码和详细说明。1. 冒泡排序 (Bubble Sort):冒泡排序是一种简单的比...【详细内容】
2024-01-17  架构师老卢  今日头条  Tags:算法   点击:(46)  评论:(0)  加入收藏
百度推荐排序技术的思考与实践
本文将分享百度在推荐排序方面的思考与实践。在整个工业界的推广搜场景上,特征设计通常都是采用离散化的设计,需要保证两方面的效果,一方面是记忆,另一方面是泛化。特征都是通过...【详细内容】
2024-01-09  DataFunTalk  微信公众号  Tags:百度推荐   点击:(78)  评论:(0)  加入收藏
什么是布隆过滤器?如何实现布隆过滤器?
以下我们介绍了什么是布隆过滤器?它的使用场景和执行流程,以及在 Redis 中它的使用,那么问题来了,在日常开发中,也就是在 Java 开发中,我们又将如何操作布隆过滤器呢?布隆过滤器(Blo...【详细内容】
2024-01-05  Java中文社群  微信公众号  Tags:布隆过滤器   点击:(91)  评论:(0)  加入收藏
面向推荐系统的深度强化学习算法研究与应用
随着互联网的快速发展,推荐系统在各个领域中扮演着重要的角色。传统的推荐算法在面对大规模、复杂的数据时存在一定的局限性。为了解决这一问题,深度强化学习算法应运而生。本...【详细内容】
2024-01-04  数码小风向    Tags:算法   点击:(100)  评论:(0)  加入收藏
非负矩阵分解算法:从非负数据中提取主题、特征等信息
非负矩阵分解算法(Non-negativeMatrixFactorization,简称NMF)是一种常用的数据分析和特征提取方法,主要用于从非负数据中提取主题、特征等有意义的信息。本文将介绍非负矩阵分解...【详细内容】
2024-01-02  毛晓峰    Tags:算法   点击:(72)  评论:(0)  加入收藏
再谈前端算法,你这回明白了吗?
楔子 -- 青蛙跳台阶一只青蛙一次可以跳上一级台阶,也可以跳上二级台阶,求该青蛙跳上一个n级的台阶总共需要多少种跳法。分析: 当n=1的时候,①只需要跳一次即可;只有一种跳法,即f(...【详细内容】
2023-12-28  前端爱好者  微信公众号  Tags:前端算法   点击:(111)  评论:(0)  加入收藏
三分钟学习二分查找
二分查找是一种在有序数组中查找元素的算法,通过不断将搜索区域分成两半来实现。你可能在日常生活中已经不知不觉地使用了大脑里的二分查找。最常见的例子是在字典中查找一个...【详细内容】
2023-12-22  小技术君  微信公众号  Tags:二分查找   点击:(79)  评论:(0)  加入收藏
强化学习算法在资源调度与优化中的应用
随着云计算和大数据技术的快速发展,资源调度与优化成为了现代计算系统中的重要问题。传统的资源调度算法往往基于静态规则或启发式方法,无法适应动态变化的环境和复杂的任务需...【详细内容】
2023-12-14  职场小达人欢晓    Tags:算法   点击:(169)  评论:(0)  加入收藏
站内最新
站内热门
站内头条