- 1机器学习概念_machine learning is fields of study that gives com
- 2国内那么多AI专业，为什么国内却没有ChatGPT？
- 3幻兽帕鲁部署，你想知道的一切_幻兽帕鲁源代码
- 4正则表达式高阶技巧之匹配模式（使用python实现）_python正则匹配
- 5oracle多表联合查询,统计查询,组函数,order by,having,子查询,集合运算_oracle三个表联查不要有空值
- 6【VSCode】Visual Studio Code软件使用入门_wpf visualstudio code
- 7RxJava使用总结_flowable.subscribeon
- 8Java中的AQS_java aqs
- 9计算机中缺失vl.dll,MSI格式安装包提示DLL缺失的权限问题
- 10Windows下安装Anaconda_windows server 2019安装anaconda
八大排序算法_选择排序是谁发明的
赞
踩
八大排序算法
分类
-
内部排序
指将需要处理的所有数据都加载到==内存存储器（内存）==中进行排序
-
外部排序
数据量过大，无法全部加载到内存中，需要借助==外部存储（文件等）==进行排序
-
常见的排序算法分类
1)稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
2)不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
3)内排序：所有排序操作都在内存中完成；
4)外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
5)时间复杂度： 一个算法执行所耗费的时间。
6)空间复杂度：运行完一个程序所需内存的大小。
7)n: 数据规模
8)k: “桶”的个数
9)In-place: 不占用额外内存
10)Out-place: 占用额外内存
冒泡排序（BubbleSort）
介绍
冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较
相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。
图解
图解过程：
- 一共进行数组大小-1次大循环
- 每一趟排序的次数在逐渐的减少
- 如果我们发现在某趟排序中，没有发生一次排序，可以提前结束冒泡排序，进行优化
代码实现
public static void bubbleSort(int[] arr) { int temp = 0; //优化，判断某趟排序中是否发生排序，默认为false boolean flag; //循环数组大小-1次 for (int i = arr.length-1; i>0 ; i--) { flag = false; for (int j = 0; j < i; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; //进行排序，将flag置为true，继续循环 flag = true; } } if (!flag) { break; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
复杂度分析
-
时间复杂度分析
元素比较的次数为︰
(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)*(N-1)/2=N2/2-N/2;元素交换的次数为︰
(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)*(N-1)/2=N2/2-N/2;总执行次数为︰
(N2/2 - N/2) + (N2/2 - N/2)=N2-N;
按照大O推导法则，保留函数中的最高阶项那么最终冒泡排序的时间复杂度为O(N2). -
空间复杂度分析 O(1).
选择排序（SelectSort）
介绍
选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。
思想
选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从arr[0] ~ arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1] ~ arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2] ~ arr[n-1]中选取最小值，与arr[2]交换，…，第i次从arr[i-1] ~ arr[n-1]中选取最小值，与arr[i-1]交换，…, 第n-1次从arr[n-2] ~ arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列
图解
说明：
-
选择排序一共有 数组大小 - 1 轮排序
-
每1轮排序，又是一个循环
2.1先假定当前这个数是最小数
2.2 然后和后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标
2.3 当遍历到数组的最后时，就得到本轮最小数和下标
2.4 交换
代码实现
public static void selectSort(int[] arr){ int min,minIndex; for (int i = 0; i <arr.length-1; i++) { min=arr[i]; minIndex = i; for (int j = i+1; j < arr.length; j++) { if (min > arr[j]){ min = arr[j]; minIndex = j; } } //下标不相等，说明发生了交换 if (minIndex!=i) { arr[minIndex] = arr[i]; arr[i] = min; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
复杂度分析
-
时间复杂度
选择排序使用了双层for循环，其中外层循环完成了数据交换，内层循环完成了数据比较，所以我们分别统计数据交换次数和数据比较次数︰
数据比较次数︰
(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)*(N-1)/2=N2-N/2;数据交换次数︰
N-1
时间复杂度: N个2/2-N/2+ (N-1 ) =N2/2+N/2-1;
根据大O推导法则，保留最高阶项，去除常数因子，时间复杂度为O(N2); -
空间复杂度O(1)
插入排序（InsertSort）
介绍
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
思想
插入排序（Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
图解
代码实现
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int insertVal = arr[i];
//有序列表最后的下标
int insertIndex = i - 1;
//从后往前进行比较，如果待插入的值小则迁移，并使比较的元素后移
while (insertIndex>=0 && insertVal<arr[insertIndex]){
arr[insertIndex+1] =arr[insertIndex];
insertIndex--;
}
arr[insertIndex+1] =insertVal;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
复杂度分析
-
时间复杂度分析
插入排序使用了双层for循环，其中内层循环的循环体是真正完成排序的代码，所以，我们分析插入排序的时间复杂度，主要分析一下内层循环体的执行次数即可。
最坏情况，也就是待排序的数组元素为{12,10,6,5,4,3,2,1}，那么︰
比较的次数为∶
(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)*(N-1)/2=N2/2-N/2;元素后移的次数为︰
(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)*(N-1)/2=N2/2-N/2;总执行次数为∶
(N2/2-N/2)+(N2/2-N/2)=N2-N;
按照大O推导法则，保留函数中的最高阶项那么最终插入排序的时间复杂度为O(N2). -
空间复杂度分析O(1)
希尔排序（ShellSort）
介绍
希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
思想
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
图解
代码实现
//交换法 public static void shellSort(int[] arr){ int temp = 0; //分组（即增量） for (int gap = arr.length/2;gap>0;gap/=2){ //使用直接插入排序 for (int i = gap; i <arr.length; i++) { //对元素进行排序 for (int j = i-gap; j >= 0; j-=gap) { if (arr[j]>arr[j+gap]){ temp = arr[j+gap]; arr[j+gap] = arr[j]; arr[j] = temp; } } } } } //移动法 public static void shellSort2(int[] arr){ int temp = 0; for (int gap = arr.length/2; gap >0 ; gap/=2) { for (int i = gap; i < arr.length; i++) { int j = i; temp = arr[i]; if (arr[j]<arr[j-gap]){ while (j-gap>=0 && temp<arr[j-gap]){ arr[j] = arr[j-gap]; j-=gap; } arr[j] = temp; } } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
复杂度分析
快速排序（QuickSort）
介绍
快速排序是对冒泡排序的一种改进。
思想
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
图解
代码实现
public static void quickSort(int[] arr,int left,int right){ int l = left; int r = right; int pivot = arr[(left+right)/2]; int temp = 0; while (l<r){ while (arr[l]<pivot){ l++; } while (arr[r]>pivot){ r--; } //已完成，说明左边已经完全小于中值，右边完全大于中值 if (l>=r){ break; } temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; //非常重要，如果没有此函数，如出现与将陷入死循环 if(arr[l] == pivot){ r--; } if (arr[r] == pivot){ l++; } } //如果r == l(即同时指向中值) 必须r--；l++，否则出现栈溢出 if (l == r) { l++; r--; } //向左递归 if (left < r){ quickSort(arr,left,r); } if (right > l){ quickSort(arr,l,right); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
复杂度分析
快速排序的一次切分从两头开始交替搜索，直到left与right重合，因此，一次切分算法的时间复杂度为O(n),但整个快速排序的时间复杂度和切分的次数相关
-
时间复杂度
- 最优情况：每次切分选择的基准数字刚好将当前序列等分
如果我们把数组的切分看做是一个树，那么上图就是它的最优情况的图示，共切分了logn次，所以，最优情况下快速排序的时间复杂度为O(nlogn);
- 1
- 最坏情况∶每一次切分选择的基准数字是当前序列中最大数或者最小数，这使得每次切分都会有一个子组，那么总共就得切分n次，所以，最坏情况下，快速排序的时间复杂度为O(n^2);
-
平均情况：每一次切分选择的基准数字不是最大值和最小值，也不是中值，这种情况我们也可以用数学归纳法证明，快速排序的时间复杂度为o(nlogn)
-
空间复杂度 O(logn)
快速排序与归并排序的区别：
快速排序是另外一种分治的排序算法，它将一个数组分成两个子数组，将两部分独立的排序。快速排序和归并排序是互补的∶归并排序将数组分成两个子数组分别排序，并将有序的子数组归并从而将整个数组排序，而快速排序的方式则是当两个数组都有序时，整个数组自然就有序了。在归并排序中，一个数组被等分为两半，归并调用发生在处理整个数组之前，在快速排序中，切分数组的位置取决于数组的内容，递归调用发生在处理整个数组之后。
归并排序（MergeSort）
介绍
归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
图解
说明：可以看到这种结构很像一棵完全二叉树，此次的归并排序采用递归去实现。分阶段可以理解为就是递归拆分子序列的过程。
再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤
代码实现
//分＋合方法 public static void mergeSort(int[] arr,int left,int right,int[] temp){ if (left<right){ int mid = (left + right)/2; //中间索引 //向左递归分解 mergeSort(arr,left,mid,temp); mergeSort(arr,mid+1,right,temp); merge(arr,left,mid,right,temp); } } /** * @param arr 排序的原始数组 * @param left 左边有序序列的初始索引 * @param mid 中间索引 * @param right 右边索引 * @param temp 做中转的数组 */ public static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i = left; //初始化i，左边有序序列的初始索引 int j = mid + 1; //初始化j，右边有序序列的初始索引 int t = 0; //指向temp数组的当前索引 //（一） //先把左右两边（有序）的数据按照规则填充到temp数组 //直到左右两边的有序序列，有一边处理完毕为止 while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[t] = arr[i]; i++; } else { temp[t] = arr[j]; j++; } t++; } //（二） //把有剩余数据一边的数据一次全部填充到temp while (i <= mid) { temp[t] = arr[i]; i++; t++; } while (j <= right) { temp[t] = arr[j]; j++; t++; } //（三） //将temp数组的元素拷贝到arr //注意，并不是每次都拷贝所有 t = 0; int tempLeft = left; //第一次合并templeft = 0，right=1 //templeft=2 right=3 //templeft=0，right=3 //最后一次 templeft=0，right=7 System.out.println("tempLeft="+tempLeft+" right="+right); while (tempLeft<=right){ arr[tempLeft] = temp[t]; t++; tempLeft++; } System.out.println(Arrays.toString(arr)); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
复杂度分析
- 时间复杂度
用树状图来描述归并，如果一个数组有8个元素，那么它将每次除以2找最小的子数组，共拆log8次，值为3，所以树共有3层,那么自顶向下第k层有2k个子数组，每个数组的长度为2(3-k)，归并最多需要2(3-k)次比较。因此每层的比较次数为2k2(3-k)=23,那么3层总共为3 23。
假设元素的个数为n，那么使用归并排序拆分的次数为log2(n).所以共log2(n)层，那么使用log2(n)替换上面 3* 23中的3这个层数，最终得出的归并排序的时间复杂度为: log2(n)* 2(log2(n))=log2(n)*n,根据大O推导法则，忽略底数，最终归并排序的时间复杂度为O(nlogn);
- 空间复杂度 O(n)
基数排序(桶排序)（RedixSort）
介绍
- 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
- 基数排序法是效率高的稳定性排序法
- 基数排序(Radix Sort)是**桶排序**的扩展
- 基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。
说明：
- 基数排序是对传统桶排序的扩展，速度很快.
- 基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError
- 基数排序时稳定的。[注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的]
- 有负数的数组，我们不用基数排序来进行排序
思想
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
图解
代码实现
//基数排序方法 public static void radixSort(int[] arr) { //1、得到数组中最大数的位数 int max = arr[0]; for (int l = 0; l < arr.length; l++) { if (arr[l] > max){ max = arr[l]; } } //等到最大数是几位数 int maxLength = (max + "").length(); //定义一个二维数组，表示10个桶，每个桶就是一个一维数组 //说明 //1、二维数组包含10个一维数组 //2、为了防止在放入数的时候，数据溢出，则每个一维数组（桶），大小定义为arr.length //3、明确，基数排序是使用空间换取时间的经典算法 int[][] bucket = new int[10][arr.length]; //为了记住每个桶中，实际存放了多少个数据，我们定义一个一维数组来记录每个桶依次放入的数据个数 //比如bucketElementCounts[0]，记录的就是bucket【0】桶的放入数据个数 int[] bucketElementCounts = new int[10]; for (int l = 0,n=1; l < maxLength; l++,n *= 10) { for (int i = 0; i < arr.length ; i++) { //取出每个元素的个位的值 int digitOfElement = arr[i] / n % 10; //放入到对应的桶中 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[i]; bucketElementCounts[digitOfElement]++; } int index = 0; for (int j = 0; j < bucketElementCounts.length; j++) { if (bucketElementCounts[j]!=0){ for (int k = 0;k < bucketElementCounts[j]; k++) { arr[index++] = bucket[j][k]; } } //第一轮处理后，需要将每个bucketElementCounts[k]=0!!!! bucketElementCounts[j] = 0; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
复杂度分析
- 时间复杂度 O(n*k)
- 空间复杂度 O(n+k)
堆排序（HeapSort）
介绍
-
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种**选择排序，**它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
-
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。
-
每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
- 一般升序采用大顶堆，降序采用小顶堆
思想
- 将待排序序列构造成一个大顶堆
- 此时，整个序列的最大值就是堆顶的根节点。
- 将其与末尾元素进行交换，此时末尾就为最大值。
- 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
- 可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了.
图解
代码实现
public static void heapSort(int[] arr) { int temp = 0; //将无序序列构成一个堆，根据升序降序需求完成大顶堆或小顶堆4 for (int i = arr.length / 2 - 1; i >= 0; i--) { adjustHeap(arr, i, arr.length); } //将堆顶元素与末尾元素进行交换，将最大元素沉到数组末端 //重新调整结构，使其满足堆定义，然后继续交换堆顶元素和当前末尾元素，反复执行调整+交换步骤，直到整个序列有序 for (int j = arr.length - 1; j > 0; j--) { temp = arr[j]; arr[j] = arr[0]; arr[0] = temp; adjustHeap(arr,0,j); } System.out.println(Arrays.toString(arr)); } //将一个数组（二叉树），调整成一个大顶堆 /** * 功能：完成将以i对应的非叶子节点的树调成大顶堆 * 举例：int[] arr = {4,6,8,5,9}; =>i=1 =>adjustHeap =>得到{4，9，8，5，6} * 如果我们再次调整adjustHeap传入的是i=0 =》得到{4，9，8，5，6} => {9，6，8，5，4} * * @param arr 待调整的数组 * @param i 表示非叶子节点在数组中的索引 * @param length 表示对多少个元素进行调整，length是在逐渐的减少 */ public static void adjustHeap(int[] arr, int i, int length) { //先取出当前节点的值，保存在临时变量 int temp = arr[i]; //开始调整 //说明 当for循环结束时，我们已经将以i为父节点的树的最大值，放在了最顶（局部） //1、 k=i*2+1 k是i节点的左子节点 for (int k = i * 2 + 1; k < length; k = k * 2 + 1) { //找出较大的子节点 if (k + 1 < length && arr[k] < arr[k + 1]) { //k指向右子节点 k++; } //判断较大子节点与父节点的大小 if (arr[k] > temp) { arr[i] = arr[k]; //i指向k，继续循环比较 i = k; } else { break; } } //将temp值放在调整后的位置 arr[i] = temp; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
复杂度分析
- 时间复杂度 O(nlogn)
- 空间复杂度 O(1)
