排序算法的介绍
排序也称排序算法(Sort Algorithm), 排序是将一组数据, 依指定的顺序进行排列的过程
排序的分类
- 内部排序
- 指将需要处理的所有数据都加载到内部存储器(内存)中进行排序
- 外部排序法
- 数据量过大, 无法全部加载到内存中, 需要借助外部存储(文件等)进行排序
- 常见的排序算法分类
算法的时间复杂度
度量一个程序(算法)执行时间的两种方法
- 事后统计的方法
- 这种方法可行, 但是有两个问题: 一是想要对设计的算法的运行性能进行评测, 需要实际运行该程序; 二是所得时间的统计量依赖于计算机的硬件,软件等环境因素,这种方式, 要在同一台计算机的相同状态下运行,才能比较那个算法速度更快
事前估算的方法
一般情况下,算法的基本操作语句的重复执行次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时, T(n) / f(n) 的极限值为不等于零的常数, 则称f(n)是T(n)的同数量级函数. 记作T(n) = O(f(n)) 称O(f(n))为算法的渐进时间复杂度,称为时间复杂度
- T(n)不同,但时间复杂度可能相同, 如: T(n) = n^2+7n+6 与 T(n) = 3n^2+2n+2 他们的T(n)不同, 但是时间复杂度相同,都为O(n^2)
- 计算 T(n) = n^2+7n+6 与 T(n) = 3n^2+2n+2
- 忽略低次项后为 T(n) = n^2 与 T(n) = 3n^2
- 忽略系数后为T(n) = n^2 与 T(n) = n^2
- 时间复杂度为 O(n^2)
计算时间复杂度的方法:
常数阶O(1)
- 对数阶O(log2n)
- 线性阶O(n)
- 线性对数阶O(nlog2n)
- 平方阶O(n^2)
- 立方阶O(n^3)
- k次方阶O(n^k)
- 指数阶O(2^n)
说明:
- 常见的算法时间复杂度由小到大依次为: O(1) < O(log2n) < O(n) < O(nlog2n) < O(n^2) < O(n^3) < O(n^k) < O(2^n),随着问题规模n的不断增大, 上述时间复杂度不断增大, 算法的执行效率越低
-
常数阶O(1)
无论代码执行多少行, 只要没有循环等复杂结构,那这个代码的时间复杂度就是 O(1)
上述代码在执行的时候,他消耗的时间并不随着某个变量的增长而增长, 那么无论这类代码有多长,即使有几万几十万行,都可以用O(1)来表示他的时间复杂度对数阶O(log2n)
x = log2^n假设n=1024那么x = 1010 的对数 = log2^1024
说明; 在while循环里面,每次都将i乘以2,乘完之后, i距离n就越来越近了,假设循环x次后, i就大于n了,此时这个循环就退出了,也就是说2的x次方等于n, 那么x = log2n,也就是说当循环log2n次以后,这个代码就结束了因此这个代码的时间复杂度为O(log2n), O(log2n)的这个2时间上是根据代码变化的, i = i * 3,则是O(log3n)
如果N = a^x(a > 0, a ≠ 1), 即a的x次方等于 N(a>0,a≠1), 那么数x叫做以a为底N的对数(logarithm),记作 想 = logaN,其中,啊叫做对数的底数, N叫做真数,x叫做以a为底N的对数线性阶O(n)
说明:这段代码,for循环里面的代码会执行n次,因此它消耗的时间是随着n的变化而变化的, 因此这类代码都可以用O(n)来表示他的时间复杂度线性对数阶O(nlog2n)
说明: 线性对数阶O(nlog2n)其实是非常容易理解的,将其时间复杂度为O(log2n)的代码循环N遍的话,那么他的时间复杂度就是n * O(log2n) 也就是 O(nlog2n)平方阶O(n^2)
说明: 平方阶O(n^2)就更容易理解了, 如果把O(n)的代码再嵌套循环一遍,他的时间复杂度就是O(n^2),这段代码其实就是嵌套了两层n循环,他的时间复杂度就是O(n n), 即O(n^2) ,如果将其中一层循环的n改成m, 那么他的时间复杂度就是O(n m)立方阶O(n^3), K方阶O(n^k)
说明:参考上面的平方阶理解就好了O(n^3)相当于循环三层n循环, 其他的类似,k方阶其实就循环k层n循环
平均时间复杂度和最坏时间复杂度
平均时间复杂度是指所有可能的输入实例均以等概率出现的2情况下,该算法的运行时间
- 最坏情况下的时间复杂度称最坏时间复杂度,一般讨论的时间复杂度均是最坏时间复杂度,这样做的原因是:最坏时间复杂度是算法在任何输入实例上运行时间的界限,这就保证了算法的运行时间不会比最坏情况更长
- 平均时间复杂度和最坏时间复杂度是否一致,和算法有关
算法的空间复杂度
基本介绍
- 类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间,他也是问题规模n的函数
- 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的度量, 有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如快速排序和归并排序算法, 基数排序就属于这种情况
在做算法分析时,主要讨论的是时间复杂度,从用户体验上看,更看重的程序执行的速度,一些缓存产品(Redis , memcache)和算法(基数排序)本质上就是用空间换时间
冒泡排序
基本介绍
冒泡排序(Bubble Sorting)的基本思想是: 通过对峙排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后面,就像水底下的气泡一样逐渐向上冒
优化:
因为排序过程中,各元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序,因此要在排序过程中设置一个标志flag判断元素是否进行过交换,从而避免不必要的比较(这里说的优化,可以在冒泡排序写好后,再进行)冒泡排序过程图解
小结上面的图解过程一共进行 数组的大小-1次大的循环
- 每一趟排序的次数在逐渐减少
- 如果我们发现在某趟排序中, 没有发生一次交换,可以提前结束冒泡排序,这个就是优化
冒泡排序应用实例
我们举一个具体的案例来说明冒泡排序,我们将5个无序的数: 3,9,-1,10,-2 使用冒泡排序将其排成一个从小到大的有序数列代码实现
```java package com.dance.sort;
import java.util.Arrays;
/**
冒泡排序 */ public class BubbleSort {
public static void main(String[] args) {
// 原数组int[] arr = {3, 9, -1, 10, -2};// 演示过程
// sortProcess(arr);
// 优化为循环 可以看见是双循环 时间复杂度在O(n^2)// sortN2(arr);
// 优化 sortN2AddFlag(arr);}
/**
- 优化
@param arr 数组 */ public static void sortN2AddFlag(int[] arr){ int temp = 0; // 定义标志位 boolean flag; for (int i = 0; i < arr.length - 1; i++) {
// 初始位设置为false flag = false; for (int j = 0; j < arr.length - 1 - i; j++) { if(arr[j] > arr[j+1]){ // 如果存在置换就记录一下 flag = true; temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } } if(!flag){ // 如果不存在置换就直接退出 break; } System.out.println("第"+(i+1)+"趟排序后的数组"); System.out.println(Arrays.toString(arr));} }
/**
- 排序 时间复杂度为 O(n^2)
@param arr 数组 */ public static void sortN2(int[] arr){ int temp = 0; for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) { if(arr[j] > arr[j+1]){ temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } } System.out.println("第"+(i+1)+"趟排序后的数组"); System.out.println(Arrays.toString(arr));} }
public static void sortProcess(int[] arr){ // 为了容易理解, 我们吧冒泡排序的演变过程,给大家展示
// 第一趟排序, 就是将最大的数排在最后, 所以只需要循环 arr.length - 1 // 临时变量 int temp = 0; for (int i = 0; i < arr.length - 1; i++) {
if(arr[i] > arr[i + 1]){ temp = arr[i + 1]; arr[i+1] = arr[i]; arr[i] = temp; }}
System.out.println(“第一趟排序后的数组”); System.out.println(Arrays.toString(arr));
// 第二趟排序 for (int i = 0; i < arr.length - 2; i++) {
if(arr[i] > arr[i + 1]){ temp = arr[i + 1]; arr[i+1] = arr[i]; arr[i] = temp; }}
System.out.println(“第二趟排序后的数组”); System.out.println(Arrays.toString(arr));
// 第三趟排序 for (int i = 0; i < arr.length - 3; i++) {
if(arr[i] > arr[i + 1]){ temp = arr[i + 1]; arr[i+1] = arr[i]; arr[i] = temp; }}
System.out.println(“第三趟排序后的数组”); System.out.println(Arrays.toString(arr));
// 第四趟排序 for (int i = 0; i < arr.length - 4; i++) {
if(arr[i] > arr[i + 1]){ temp = arr[i + 1]; arr[i+1] = arr[i]; arr[i] = temp; }}
System.out.println(“第四趟排序后的数组”); System.out.println(Arrays.toString(arr)); } } ```
排序过程
比较过程
选择排序
基本介绍
选择式排序也属于内部排序法,是从欲排序的数据中,按指定的规则选出某一元素,再依规定交换位置后达到排序的目的
选择排序思想
选择排序(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次,得到一个按排序码从小到大排列的有序序列
选择排序思路分析图
- 对一个数组的选择排序再进行讲解
选择排序应用实例
有一群牛,颜值分别是101,34,119,1 请使用选择排序从低到高进行排序[101,34,119,1]
代码实现
package com.dance.sort;
import java.util.Arrays;
/**
* 选择排序
*/
public class SelectSort {
public static void main(String[] args) {
int[] arr = {101, 34, 119, 1, 11, -2, 13};
selectProcess(arr);
}
/**
* 使用逐步推导的方式来,讲解选择排序
*
* @param arr 原始数组
*/
public static void selectProcess(int[] arr) {
// 第一轮
// 原始的数组 101, 34, 119, 1
// 第一轮的排序 1, 34, 119, 101
// 第二轮的排序 1, 34, 119, 101
// 第二轮的排序 1, 34, 101, 119
// 算法 -> 先简单 -> 再复杂, 就是可以把一个复杂的算法,拆分成简单的问题,逐步解决
for (int i = 0; i < arr.length - 1; i++) {
int jIndex = i;
int jValue = arr[i];
for (int j = i + 1; j < arr.length; j++) {
if(arr[j] < jValue){
jIndex = j;
jValue = arr[j];
}
}
if(jIndex != i){
arr[jIndex] = arr[i];
arr[i] = jValue;
}
System.out.println("第"+(i+1)+"次排序后的结果");
System.out.println(Arrays.toString(arr));
}
}
}
排序过程
比较过程
插入排序
插入排序介绍
插入式排序属于内部排序法,是对于欲排序的元素以插入的方式寻找该元素的位置,以达到排序的目的
插入排序思想
插入排序(insertion sorting) 的基本思想是: 把N个待排序的元素看成一个有序表和无序表,开始时有序表中只包含一个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表
插入排序思路图
插入排序应用实例
有一群小妞,考试成绩分别是101,34,119,1 请使用插入排序法按照从小到大进行排序
代码实现
package com.dance.sort;
import java.util.Arrays;
/**
* 插入排序
*/
public class InsertionSort {
public static void main(String[] args) {
int[] arr = {101, 34, 119, 1, 89, -2};
insertSort(arr);
}
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
// 定义待插入的数, 从1开始
int insertVal = arr[i];
// 和i-1比较
int insertIndex = i - 1;
// 开始循环 expression 索引 >= 0 && 待插入的值 < 当前值
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
// 如果小于 当前值(i-1)后移一位
arr[insertIndex + 1] = arr[insertIndex];
// (i-1) --
insertIndex--;
}
// 当退出while循环时,说明找到插入的位置, insertIndex + 1
// 判断是否需要赋值
if((insertIndex + 1) != i){
arr[insertIndex + 1] = insertVal;
}
System.out.println("第"+i+"轮插入后");
System.out.println(Arrays.toString(arr));
}
}
}
排序过程
比较过程
希尔排序
简单插入排序存在的问题
我们看简单的插入排序可能存在的问题
数组 arr = {2,3,4,5,6,1} 这时需要插入的数1,最小,这样的过程是:
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
结论: 当需要插入的数较小,且位于数组的下标越大,后移的次数明显增多,对效率有影响
希尔排序介绍
希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法,希尔排序也是一种插入排序,,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序
希尔排序基本思想
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序,随着增量逐渐减少,每组包含的关键词越来越多,,当增量减到1时,整个文件恰被分成一组,算法被终止
希尔排序示意图
希尔排序应用实例
有一群小牛,考试成绩分别是{8,9,1,7,2,3,5,4,6,0}, 请从小到大排序,请分别使用
import java.util.Arrays;
/**
希尔排序 */ public class ShellSort {
public static void main(String[] args) {
int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};// shellSort(arr);
shellSortFor(arr);}
/**
- 交换法 *
@param arr 原始数组 */ public static void shellSort(int[] arr) { int temp; // 第一轮排序将 10个 数据 分成10 / 2 = 5 组 for (int i = 5; i < arr.length; i++) {
// 遍历各个数组的所有元素(共5组,每组有2个元素),步长5 for (int j = i - 5; j >= 0; j -= 5) { // 如果当前元素大于加上步长后的那个元素,说明交换 if (arr[j] > arr[j + 5]) { temp = arr[j]; arr[j] = arr[j + 5]; arr[j + 5] = temp; } }} System.out.println(“希尔排序第一轮后:” + Arrays.toString(arr));
// 第二轮排序将 10个 数据 分成5 / 2 = 2 组 for (int i = 2; i < arr.length; i++) {
// 遍历各个数组的所有元素(共5组,每组有2个元素),步长5 for (int j = i - 2; j >= 0; j -= 2) { // 如果当前元素大于加上步长后的那个元素,说明交换 if (arr[j] > arr[j + 2]) { temp = arr[j]; arr[j] = arr[j + 2]; arr[j + 2] = temp; } }} System.out.println(“希尔排序第二轮后:” + Arrays.toString(arr));
// 第三轮排序将 10个 数据 分成2 / 2 = 1 组 for (int i = 1; i < arr.length; i++) {
// 遍历各个数组的所有元素(共5组,每组有2个元素),步长5 for (int j = i - 1; j >= 0; j--) { // 如果当前元素大于加上步长后的那个元素,说明交换 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } }} System.out.println(“希尔排序第三轮后:” + Arrays.toString(arr)); }
public static void shellSortFor(int[] arr) { // 每次除以2 // 10/2=5/2=2/2=1/2=0 int temp; int count = 1; for (int gap = arr.length / 2; gap > 0; gap /= 2) {
// 第一轮排序将 10个 数据 分成10 / 2 = 5 组 for (int i = gap; i < arr.length; i++) { // 遍历各个数组的所有元素(共5组,每组有2个元素),步长5 for (int j = i - gap; j >= 0; j -= gap) { // 如果当前元素大于加上步长后的那个元素,说明交换 if (arr[j] > arr[j + gap]) { temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp; } } } System.out.println("希尔排序第"+(count++)+"轮后:" + Arrays.toString(arr));} } }
<a name="MmUtW"></a> ## 排序过程&&比较过程[交换法]  <a name="zWMBy"></a> ## 代码实现[移动法] ```java public static void shellSortMove(int[] arr) { int count = 1; // 增量gap,逐渐缩量 for (int gap = arr.length / 2; gap > 0; gap /= 2) { // 5 5<10 5++ for (int i = gap; i < arr.length; i++) { // 5 6 7 8 9 // 记录索引位置 int index = i; // 3 5 4 6 0 int temp = arr[i]; // 减去增量gap 5-5 // 3 5 4 6 0 < 8 9 1 7 2 if (arr[i] < arr[index - gap]) { // 3 < 8 // 0-- 1-- 2-- 3-- 4-- // && // 5 6 7 8 9 0 1 2 3 4 index // 3 5 4 6 0 < 8 9 1 7 2 val while (index - gap >= 0 && temp < arr[index - gap]) { // index 后移 // 8 -> 3 val // 0 -> 5 index // 把索引0位置的8赋值到索引5上 arr[index] = arr[index - gap]; // index -- // 5 - 5 0 // 6-5 1 5-5 0 // 2 1 0 // 3 2 1 0 // 4 3 2 1 0 index -= gap; } // 5-5 0 // 6-5 1 // 7-5 2 // 8-5 3 // 9-5 4 arr[index] = temp; } } System.out.println("第" + (count++) + "次循环后" + ":" + Arrays.toString(arr)); } }理解
自我感觉就是两种交换法和移动法,前几次的时间都是一致的,只有最后一次,交换法很慢,
最后一次
第一遍: 0 - 1
第二遍: 1 - 2 0 - 1
第三遍: 2 - 3 1 - 2 0 - 1
…..
会有很多重复的对比
而移动法是
最后一次
循环中移动,因为前几次的分组就是为了将数组变得大致有序,这样移动法的交换次数就少很多,所以效率比交换法高
排序过程&&比较过程
排序过程和比较过程参考交换法,第一,第二圈,第三圈参考插入排序
快速排序
快速排序介绍
快速排序(QuickSort)是对冒泡排序的一种改进,基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按照此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列
快速排序示意图
快速排序应用实例
要求: 对{-9,78,0,23,-567,70} 进行从小到大的排序,要求使用快速排序
说明[验证分析]
- 如果取消左右递归,,结果是 -9,-567,0,23,78,70
- 如果取消右递归,结果是 -567 -9 0 23 78 70
- 如果取消左递归,结果是 -9 -567 0 23 70 78
代码实现
```java package com.dance.sort;
import java.util.Arrays;
public class QuickSort { public static void main(String[] args) { int[] arr = {-9, 78, 0, 23, -567, 0}; quickSort(arr, 0, arr.length - 1); System.out.println(“arr=” + Arrays.toString(arr)); }
public static void quickSort(int[] arr, int left, int right) {
int l = left; // 左下标
int r = right; // 右下标
// 中下标 取值
int middle = arr[(l + r) / 2];
int temp = 0;
while (l < r) {
while (arr[l] < middle) {
l++;
}
while (arr[r] > middle) {
r--;
}
if (l >= r) {
break;
}
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
if (arr[l] == middle) {
r--;
}
if (arr[r] == middle) {
l++;
}
}
if (l == r) {
l++;
r--;
}
if (left < r) {
quickSort(arr, left, r);
}
if (right > l) {
quickSort(arr, l, right);
}
}
排序过程&比较过程
归并排序
若有收获，就点个赞吧
0 人点赞
