目录
排序的分类
算法的时间复杂度
1） 时间频度
2）时间复杂度
3） 常见的时间复杂度
4） 平均时间复杂度和最坏时间复杂度
冒泡排序
选择排序
插入排序
希尔排序
快速排序
归并排序
基数排序（桶排序）
基数排序算法的注意事项
常用排序算法总结和对比
排序的分类
算法的时间复杂度
1） 时间频度
一个算法花费的时间与算法中语句执行的次数成正比例
一个算法中的语句执行次数称为语句频度（时间频度）记作T(n)【可忽略常数项，低次项，忽略最高次项的系数】
2）时间复杂度
3） 常见的时间复杂度
4） 平均时间复杂度和最坏时间复杂度
平均复杂度：所有可能的输入实例以等概率出现的情况下，该算法的运行时间
最坏情况下的时间复杂度：任何输入实例上运行的时间界限，保证了算法的运行时间不会比最坏情况更长
5）算法的空间复杂度
冒泡排序
优化：如果我们在某一趟排序中，没有发生一次交换，可以提前结束冒泡排序
package com.tt12.sort;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int arr[] = {3, 9, -1, 10, 20};
int temp = 0;
boolean flag = false; //优化 表示是否进行过交换
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]) {
flag = true;
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
System.out.println("第" + i+1 + "趟" + Arrays.toString(arr));
if(!flag) {
//一次交换都没有发生
break;
} else {
flag = false; //重置flag进行下一次判断
}
}
}
}
选择排序
优化：如果最小的就是最开始假定的最小值 就省去交换的步骤
package com.tt12.sort;
import java.util.Arrays;
public class SelectSort {
public static void main(String[] args) {
int arr[] = {101, 34, 119, 1};
//1,34,119,101
//1,34,119,101
//1,34,101,119
selectSort(arr);
}
public static void selectSort(int[] arr) {
for (int j = 0; j < arr.length - 1; j++) {
int minIndex = j;
int min = arr[j];
for (int i = j + 1; i < arr.length; i++) {
if (min > arr[i]) {
minIndex = i;
min = arr[i];
}
}
if(minIndex != j) {
//优化，如果最小的就是最开始假定的最小值 就省去交换的步骤
arr[minIndex] = arr[j];
arr[j] = min;
}
System.out.println("第" + (j + 1) + "次" + Arrays.toString(arr));
}
}
}
插入排序
package com.tt12.sort;
import java.util.Arrays;
public class InsertSort {
public static void main(String[] args) {
int[] arr = {101, 34, 119, 1};
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
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--;
}
//退出循环说明找到了插入的位置，insertIndex + 1
arr[insertIndex + 1] = insertVal;
}
}
}
当需要插入的数是比较小的数时，后移的次数明显增多，对效率有影响，因此提出希尔排序
希尔排序
也是一种插入排序，简单插入排序经过改进，也称为 “缩小增量排序”
在希尔排序时，1.对有序序列在插入时采用交换法
2.对有序序列在插入时采用移动法
package com.tt12.sort;
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);
}
//对有序序列在插入时采用交换法
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];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
}
//对有序序列在插入时采用移动法
public static void shellSort2 (int[] arr) {
for(int gap = arr.length / 2; gap > 0; gap = 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循环说明找到了位置
arr[j] = temp;
}
}
}
}
}
快速排序
package com.tt12.sort;
import java.text.SimpleDateFormat;
import java.util.Date;
public class QuickSort {
public static void main(String [] args) {
//速度测试
int[] arr = new int[8000000];
for(int i = 0; i < 8000000; i++) {
arr[i] = (int) (Math.random() * 8000000);
}
Date data1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(data1);
System.out.println("排序前的时间时" + date1Str);
quickSort(arr,0,arr.length - 1);
Date data2 = new Date();
String date2Str = simpleDateFormat.format(data2);
System.out.println("排序前的时间时" + date2Str);
}
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 += 1;
}
while(arr[r] > pivot) {
r -= 1;
}
if(l >= r) {
//说明pivot左边全是小于和等于pivot的值 右边
break;
}
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
//如果交换玩后发现arr[l] == pivot
if(arr[l] == pivot) {
r--;
}
if(arr[r] == pivot) {
l++;
}
}
if(l == r) {
l += 1;
r -= 1;
}
if(left < r) {
quickSort(arr,left,r);
}
if(right > l) {
quickSort(arr,l,right);
}
}
}
归并排序
基数排序（桶排序）
基数排序算法的注意事项
常用排序算法总结和对比
