一、八种重要的内部排序
二、常见的时间复杂度
说明：
Ο(1)： 一句话就搞定；
Ο(log2__n)：对数运算;
Ο(n)：单层for循环；
Ο(nlog2__n)：线性和对数相结合的运算；
Ο(_n_2)：双重嵌套循环；
Ο(_n_3)：三层嵌套循环；
Ο(_n_k)：K层嵌套循环；
Ο(_2_n) ：
•常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2__n)＜Ο(n)＜Ο(nlog2__n)＜Ο(_n_2)＜Ο(_n_3)＜ Ο(_n_k) ＜Ο(_2_n) ，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低
•从图中可见，我们应该尽可能避免使用指数阶的算法
1. 时间复杂度示例
三、冒泡排序（Bubble Sorting）
1. 图解冒泡过程
一句话总结：每次产生最大的一个数调整到最后，所以一共执行的次数是：（n-1）(n-2)(n-3)…1 次， 时间复杂度是： O(n2)
package com.atguigu.sort;public class BubbleSortDemo {public static void main(String[] args) {int[] arr = {3, 9, -1, 10, -2};// 设置临时变量做交换的时候用int temp = 0;for (int j = 0; j < arr.length - 1; j++) {for (int i = 0; i < arr.length - 1 - j; i++) {if (arr[i] > arr[i + 1]) {temp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = temp;}}}}}
2. 代码的优化：
做一个标识，如果发现某次顺序没有发生变化，则说明顺序正确，可以提前停止
// 将前面的冒泡排序封装成一个方法
public static void bubbleSortFun(int[] arr){
// 做一个标识，如果发现某次顺序没有发生变化，则说明顺序正确，可以提前停止
boolean flag=false;
// 设置临时变量做交换的时候用
int temp = 0;
for (int j = 0; j < arr.length - 1; j++) {
for (int i = 0; i < arr.length - 1 - j; i++) {
if (arr[i] > arr[i + 1]) {
flag=true;
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
if(!flag){ // 说明在一次循环过程中，代码没有交换过
break;
}else {
flag=false; // 重置flag进行下次判断
}
}
System.out.println(Arrays.toString(arr));
}
3. 创建时间格式：
Date date1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(date1);
System.out.printf("排序之前的时间:%s",date1Str);
四、选择排序
1. 逻辑
2. 代码实现
//选择排序的方法(每次选最小值)
public static void selectSortFun(int[] arr){
for (int i = 0; i < arr.length-1; i++) {
// 设置变量，标记最小值和对应的下标
int minIndex = i; // 每次假设第i个位置的数据是最小的，不过不是，则需要调换，如果是，则保持不变，进行下一轮
int minValue = arr[i];
for (int j = i+1; j < arr.length; j++) {
if(minValue > arr[j]){
minValue=arr[j];
minIndex=j;
}
}
// 如果当前的最小值和最小下标就是此次循环的初始设置值，则不做任何改变
if(minIndex!=i){
arr[minIndex] = arr[i]; // 第i轮，是和第i个位置的数值进行交换
arr[i]=minValue;
}
}
}
五、冒泡和选择排序时间复杂度
六、插入排序
1. 核心思想
把原始数组分为2部分，前面为有序的，后面是无序的。所以一般选择第一个元素作为子数组，即有序数组。
在当前数组中，从第二个数开始，和前面的数进行比较，使之放在正确的位置上；
2. 代码实现
public static void insertSort(int[] arr) {
int tempValue = 0;
for (int i = 1; i < arr.length; i++) {
for (int j = i; j >= 1; j--) {
if (arr[j] < arr[j - 1]) {
tempValue = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tempValue;
} else {
break;
}
}
}
}
// 方法二：时间复杂度更低
// 中心思想：当前值与之前所有的值都逆序比较，当之前的值大于当前值时，用之前为止的值替换此位置的值（意味着每个位置值只交换一次）
//插入排序
public static void insertSort(int[] arr) {
int insertVal = 0;
int insertIndex = 0;
//使用for循环来把代码简化
for(int i = 1; i < arr.length; i++) {
//定义待插入的数
insertVal = arr[i];
insertIndex = i - 1; // 即arr[1]的前面这个数的下标
// 给insertVal 找到插入的位置
// 说明
// 1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界
// 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
// 3. 就需要将 arr[insertIndex] 后移
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
insertIndex--;
}
// 当退出while循环时，说明插入的位置找到, insertIndex + 1
// 举例：理解不了，我们一会 debug
//这里我们判断是否需要赋值
if(insertIndex + 1 != i) {
arr[insertIndex + 1] = insertVal;
}
//System.out.println("第"+i+"轮插入");
//System.out.println(Arrays.toString(arr));
}
}
3. 时间复杂度
Ο(_n_2)
问题：当出现较小的值时，该值前面所有的数都得重新调换位置（第二个for循环），影响效率。《——希尔排序
七、希尔排序（缩小增量排序）
1. 核心思想
2. 代码实现（交换法）
public static void shellSortFun(int[] arr){
int tempValue = 0;
for(int stepSize = arr.length/2;stepSize>0;stepSize /=2){ // 直到stepSize = 1为止
for(int i=stepSize;i<arr.length;i++){
// 每组元素中的下标步长
for(int j=i-stepSize;j>=0;j-=stepSize){
// 如果当前元素大于加上步长后的那个元素，则交换位置
if(arr[j]>arr[j+stepSize]){
tempValue = arr[j];
arr[j]=arr[j+stepSize];
arr[j+stepSize]=tempValue;
}
}
}
}
}
3. 更高效的代码实现（移位方法）
//对交换式的希尔排序进行优化->移位法
public static void shellSort2(int[] arr) {
// 增量gap, 并逐步的缩小增量
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
// 从第gap个元素，逐个对其所在的组进行直接插入排序
for (int i = gap; i < arr.length; i++) {
int j = i;
int temp = arr[j];
if (arr[j] < arr[j - gap]) {
while (j - gap >= 0 && temp < arr[j - gap]) {
//移动
arr[j] = arr[j-gap];
j -= gap;
}
//当退出while后，就给temp找到插入的位置
arr[j] = temp;
}
}
}
}
八、快速排序
1. 核心思想
是对冒泡排序的改进
逻辑思维参考链接：https://www.jb51.net/article/211611.htm
把左边和右边的位置中不合要求的元素对调位置。
然后把变量i\j对应的位置和基准值进行对比，对调位置；
2. 代码实现
public class QuickSort {
public static void quickSort(int[] arr,int low,int high){
int i,j,temp,t;
if(low>high){
return;
}
i=low;
j=high;
//temp就是基准位
temp = arr[low];
while (i<j) {
//先看右边，依次往左递减
while (temp<=arr[j]&&i<j) {
j--;
}
//再看左边，依次往右递增
while (temp>=arr[i]&&i<j) {
i++;
}
//如果满足条件则交换
if (i<j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort(arr, low, j-1);
//递归调用右半数组
quickSort(arr, j+1, high);
}
public static void main(String[] args){
int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
quickSort(arr, 0, arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
3. 时间复杂度
速度很快
九、归并排序
1. 核心思想
2. 代码实现
package com.atguigu.sort;
import java.util.Arrays;
public class MergeSortDemo {
public static void main(String[] args) {
int[] arr = {9,8,7,6,5,4,3,2,1};
int[] temp = new int[arr.length];
mergeSortFun(arr, 0, arr.length-1, temp);
System.out.println(Arrays.toString(arr));
}
// 分+合的方法
public static void mergeSortFun(int[] arr,int left, int right,int[] temp){
// step1: 先把原数组拆分成子数组，分别是left和right
// step2: 子数组形成有序数组
// step3: 子数组合并成大的完整有序数组
if(left<right){
int mid = (left+right)/2;
// 左递归分解
mergeSortFun(arr, left, mid, temp);
// 向右递归进行分解
mergeSortFun(arr, mid+1, right, temp);
// 每分解一次就合并一次
merge(arr, left, mid,right,temp);
}
}
// 合并的方法
/**
* @param arr 初始的数组
* @param left 左边有序子数组初始索引
* @param mid 右边子数组的前一位的下标值， 也就是left的最后一个元素的下标值
* @param right 右边有序子数组初始索引
* @param temp 用于存储的临时有序数组
*/
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left; // 左边有序序列的初始索引
int j = mid + 1; // 右边有序序列的初始索引
int t = 0; // 指向temp数组的当前索引
//step1: 先把左右两边的有序数据逐一取出来进行对比，较小的值进入temp数组，直到左右两边有一边处理完毕
while (i <= mid && j <= right) {
// 说明工作还没有结束
if (arr[i] <= arr[j]) {
temp[t] = arr[i];
i++;
} else {
temp[t] = arr[j];
j++;
}
t++;
}
// step2: 把有剩余的数组的元素全部拷贝到temp中去
//说明右边的遍历完了，把左边剩余部分直接加入到temp中
while (i <= mid) {
temp[t] = arr[i];
t += 1;
i += 1;
}
while (j <= right) {
temp[t] = arr[j];
t += 1;
j += 1;
}
// step3: 把temp中的元素全部拷贝到arr中去，替换原来的数据
// 注意： 是每次把单独的小数组合并到原始的大数组中去
t = 0; // temp数组的下标
int tempLeft = left; // left是最初传入的，其代表原始数组中元素的下标
while(tempLeft<=right){
arr[tempLeft]=temp[t];
t++;
tempLeft++;
}
}
}
十、基数排序
1. 逻辑思维
2. 代码实现
step1: 获取个位上的数： element%10
step2: 获取十位数上的数： element/10%10
step3: 获取百位上的数： element/100%10
// 获取最大数的位数
int max = arr[0]; // 初始化，假设位置为0的数字最大
// 获取最大值
for (int value : arr) {
max = Math.max(max, value);
}
// 获取最大值的位数
int maxLength = (max+"").length();
package com.atguigu.sort;
public class RadixSortDemo {
public static void main(String[] args) {
}
public static void radixSort(int[] arr){
// 获取最大数的位数
int max = arr[0]; // 初始化，假设位置为0的数字最大
// 获取最大值
for (int value : arr) {
max = Math.max(max, value);
}
// 获取最大值的位数
int maxLength = (max+"").length();
// 第一轮（针对个位数上）
// 定义一个二维数组，表示10个桶，每个桶就是一个一维数组
/**
* 1. 二维数组包含10个一维数组
* 2.为了防止放数的时候数据溢出，每个一维数组的大小设定为arr.length个
* 3. 所以基数排序是用空间换时间的经典案例
*/
// 每个桶都需要有个指针，表明当前桶里放了几个有效数据
int[][] bucket = new int[10][arr.length];
// 定义一个一维数组，记录实际每个桶放了多少数据
int[] bucketElementCount = new int[10];
for (int j = 0,n =1; j < maxLength; j++,n *=10) {
//j代表第几轮
for (int i : arr) {
// 取出每个元素的个位
int digitOfElement = i/n%10; // 取余
// 放入到对应的桶中
bucket[digitOfElement][bucketElementCount[digitOfElement]] = i;
bucketElementCount[digitOfElement]++;
}
// 按照桶的顺序，依次取值，放入到原来的数组中（覆盖掉原数组中的数据）
int index = 0;
for (int k = 0; k < bucketElementCount.length; k++) {
// 如如果桶中有数据，我们才放入到原数组中
if(bucketElementCount[k]!=0){
for (int l = 0; l < bucketElementCount[k]; l++) {
// 取出元素放入到arr中
arr[index]=bucket[k][l];
index++;
}
}
// 第一轮处理后，需要将每个bucketElementCounts[k]=0,即将桶清空
bucketElementCount[k]=0;
}
}
}
}
3. 时间复杂度
运算速度非常快，但是消耗内存
十一、排序时间复杂度的比较
若有收获，就点个赞吧
0 人点赞
