- 排序的种类
- 时间频度和特点
- 时间复杂度
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
- 快速排序
- 归并排序
- 基数排序
- 堆排序
以下只给出思路与关键方法，算法的源代码放在了git中，需要的自取
排序的种类
排序分为内部排序和外部排序
一般为内部排序，可以划分为8大排序
插入排序：直接插入 | 希尔排序
选择排序：简单选择 | 堆排序
交换排序：冒泡排序 | 快速排序
归并排序（分治算法）
基数排序（桶排序）
时间频度和特点
1、常数项可以忽略
2、低次方项可以忽略
3、次方项的系数可以忽略
时间复杂度
1、一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大的时候，T(n) / f(n)的极限值为不等于0的常数，则称f(n)是T(n)的同数量级函数，记作T(n) = O(f(n))， O(f(n))称为算法的渐进时间复杂度，简称时间复杂度
2、T(n)不同，但时间复杂度可能相同
计算方法
用常数1表示运行中所有加法常数
只保留最高阶项
去掉最高阶的系数
常用的时间复杂度
由小到大
常数阶O(1)：没有循环等复杂结构
对数阶O(log2n)：if（i < n）一直循环 i = i * 2，n多大执行log2n遍，也就是说2^次数=n，次数=log2n
线性阶O(n)：i++或者一层for循环，都是一个意思，n多大执行多少遍
线性对数阶O(nlog2n)：for循环中套了一个对数阶
平方阶O(n^2)：两层for循环
立方阶O(n^3)：三层for循环
k次方阶O(n^k)：n层for循环
指数阶O(2^n)：
图片来源于网络
冒泡排序
思想：两个for循环，比数组大小-1次，每次比较数组大小-1次，从数组的第一个数字开始与下一个比较，如果第一个比第二个大则交换，否则第二个跟第三个比较
代码实现
//冒泡排序
public static void sort(int[] a) {
//只能用于判断趟数，省趟数，不省次数
boolean flag = true;
for (int i = 0; i < a.length - 1; i++) {
//排序n - 1趟
for (int j = 0; j < a.length - 1 - i; j++) {
if (a[j] > a[j+1]) {
swag(a,j,j+1);
flag = false;
}
}
if (flag) {
break;
} else {
//不重置只要交换过就没用了
flag = true;
}
}
}
复制代码选择排序
思想
将数组中的数据遍历，先拿第一个进行比较，看后面的有没有比这更小的，有的话交换，没有就第二个进行比，依次比较，一共需要比数组大小-1次
代码实现
private static void sort(int[] a) {
for (int i = 0; i < a.length-1; i++) {
for (int j = i; j < a.length-1; j++) {
if (a[j+1] < a[i]) {
//交换两数
swag(a,i,j+1);
}
}
}
}
复制代码插入排序
思想：将一个数组中的数据看作两个数组，有序和无序数组，由于第一个无需比较，所以需要比n-1次，将无需数组的第一个与有序数组的最后一个依次对比，并且插入合适的位置
一个for循环，一个while解决
初始为数组的第二个元素，依次与前面的比较，如果小的话一直比，直到遇到大的，则将找到的该元素后移，将比较的元素插入找到元素的后面，一轮结束，一共需要数组大小-1轮比较
图片来源于网络
代码实现
private static void sort(int[] a) {
for (int i = 0; i < a.length-1; i++) {
int arr = a[i+1];
int index = i;
while (index >= 0 && arr < a[index]) {
a[index + 1] = a[index];
index--;
}
a[index+1] = arr;
}
}
复制代码希尔排序
如果存在一个数组为{2，3，4，5，6，1}那么使用插入排序会导致算法效率很慢
所以说是对插入排序的一种优化，它是分组对每组进行排序，又叫做缩小增量排序
图片来源于网络
为什么希尔排序效率更高
由于开始时，步长的取值较大，每个子序列中的元素较少，排序速度较快，到排序后期步长取值逐渐变小，子序列中元素个数逐渐增多，但由于前面工作的基础，大多数元素已经基本有序，所以排序速度仍然很快。就是判断的多了，移动的次数变少，所以速度变快。
代码实现
private static void shellSort(int[] a) {
int count = 0;
for (int gap = a.length /2; gap > 0; gap /= 2) {
for (int i = gap; i < a.length; i++) {
int index = i;
int arr = a[index];
if (arr < a[index-gap]) {
while (index - gap >= 0 && arr < a[index-gap]) {
count ++ ;
a[index] = a[index-gap];
index-=gap;
}
a[index] = arr;
}
}
}
System.out.println("一共："+count+"次");
}
int[] a = {4,3,5,2,1,9,8,10,7,6};
复制代码同样的数组，用插入需要16次，用希尔只需要8次
快速排序
特点就是递归，通过一个中间数，将该数的左右分别排序好，先找一个基准值，一般为数组大小/2，左边找到一个比基准值大的数，右边找到一个比基准值小的数，然后进行交换，算完之后左边的都为比基准值小的，右边都为比基准值大的，但不能保证他们是有序的，所以还需要对左右生成的数据进行二次排序
代码实现
private static void sort(int left, int right, int[] arr) {
int l = left;
int r = right;
int center = arr[(l+r)/2];
int temp = 0;
while (l < r) {
while (arr[l] < center) {
l += 1;
}
while (arr[r] > center) {
r -= 1;
}
if (l >= r) {
break;
}
//交换顺序，指针改变
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
l+=1;
r-=1;
}
if (l == r) {
l+=1;
r-=1;
}
if (left < r) {
sort(left,r,arr);
}
if (right > l) {
sort(l,right,arr);
}
}
}
复制代码归并排序
归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
分而治之
图片来源网络
图片来源网络
思想
先将数组中的一组数据进行划分，最后去比较划分好的数据然后逐级比较合并
代码实现
private static void sort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
//左归并
sort(arr, left, mid);
//右归并
sort(arr, mid + 1, right);
//归并计算
merge(arr, left, mid, right);
}
}
private static void merge(int[] arr, int left, int mid, int right) {
count ++ ;
int i = left;
int j = mid + 1;
int[] temp = new int[right-left+1];
int t = 0;
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
//左边小，将左边的数放入数组中
temp[t++] = arr[i++];
}else {
//右边小，将右边的数据放入数组中
temp[t++] = arr[j++];
}
}
//将剩下的数据放入数组中
while (i <= mid) {
temp[t++] = arr[i++];
}
while (j <= right) {
temp[t++] = arr[j++];
}
//将temp的数据放入arr中
t = 0;
while (t < temp.length) {
arr[left++] = temp[t++];
}
}
}
复制代码基数排序
图片来源于网络
难点
1、取数组内最大数字的位数
2、求次方
3、求本次遍历应该取个位还是什么位，如何取
4、桶应该如何创建
代码实现
private static void sort(int[] arr) {
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int size = (max + "").length();
/**
* size表示循环的次数，根据最大数的位数决定，n表示当前应该取哪一位数，n为1的时候表示取个位
* n为10表示取百位，以此类推，每次遍历都创建一个length*10的桶，保证数据不会出错
* 存的时候是按照行列存储的，但取得时候按照列行取（按照人的思维）
*/
for (int k = 0, n = 1; k < size; k++, n *= 10) {
//创建一个二维数组用来表示放置的桶
int[][] bucket = new int[arr.length][10];
for (int i = 0; i < arr.length; i++) {
int temp = arr[i];
int gewei = temp / n % 10;
bucket[i][gewei] = temp;
}
int t = 0;
for (int i = 0; i < 10; i++){
for (int j = 0; j < arr.length; j++){
if (bucket[j][i] != 0) {
arr[t++] = bucket[j][i];
}
}
}
System.out.println(Arrays.toString(arr));
}
}
复制代码堆排序（用顺序存储二叉树的思想进行排序）
相关概念
堆这种数据结构是一种排序算法，堆排序是一种选择排序，它的最坏最好，平均复杂度均未nlogn，为不稳定排序
大顶堆：每个结点的值都大于等于他的左右孩子结点的值，比如下图
小顶堆：相反，每个结点的值都小于等于他的左右孩子结点的值，比如下图
大小是对于顶点来说的，一般大顶堆做升序，小顶堆做降序
堆排序思想
如果是升序，也就是从小到大排，那么就需要构建大顶堆，然后想根节点元素与最后一个叶子进行交换，重复除了已经筛选好的叶子节点这个过程
也可以说将数组按照树的思想进行排序。树只是一个逻辑上的概念
步骤，刚开始如下图
1、首先找到第一个非叶子节点，公式 a.length / 2 – 1，将叶子结点大的值进行交换
2、然后在找到下一个非叶子节点重复1的操作
3、排完在返回来进行之前左子树的排序，因为结构已经混乱（程序不用递归怎么回来的，在上一步已经做了遍历操作，可以看作23是一起的）
4、最后形成一个大顶堆，将堆顶元素与最后一个叶子节点交换值，除去该值，继续重复上面的过程
5、重新调整结构，继续构建大顶堆
6、重复进行
难点
1、构建大顶堆 / 构建小堆顶
2、边界值判断
自己思路写出的代码如下，完了思考这个复杂度怎么都上n2了啊
public class HeapSort {
public static void main(String[] args) {
int[] a = {4,6,8,5,9};
System.out.println("排序前:"+ Arrays.toString(a));
sort(a);
System.out.println("排序后:"+ Arrays.toString(a));
}
/**
* 构建大顶堆（升序）
* @param a 待处理的数组
* @param i 待处理非叶子节点
* @param length 待处理数组的长度
*/
private static void heapSort(int[] a, int i, int length) {
while (i >= 0) {
//从该节点的索引下进行调整，将i节点之下构建为一个大顶堆
for (int j = 2 * i + 1; j <= length; j = j * 2 + 1) {
//此时j为左子树
if (j+1 <= length && a[j] < a[j+1]) {
//若左子树大于右子树，则挪动指针，指向右子树
j++;
}
if (a[i] < a[j]) {
//将大元素放置顶堆
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
i--;
}
}
private static void sort(int[] a) {
//构建大顶堆
for (int length = a.length - 1; length > 0; length--) {
heapSort(a, length / 2 - 1, length);
//将堆顶堆底元素互换
int temp = a[0];
a[0] = a[length];
a[length] = temp;
}
}
}
复制代码改进版（逻辑上更好理解了，老师的思路，但复杂度我觉得没有达到nlogn）
1、先构建大顶堆，然后在进行堆顶元素的顺序调整，一个需要遍历数组个数-1次，剩下那个自动就是有序的，所以为for (int j = a.length; j > 1; j–) {}
2、构建大顶堆思路，先用临时变量存入索引值，然后与子树进行比较大小，当指针确定所以节点子树位置后，与所以节点的值进行比较，比索引大则赋值，最后将原先索引的值放置子树节点位置
代码实现
private static void adjustSort(int[] a) {
//构建大顶堆
for (int j = a.length; j > 1; j--) {
for (int i = a.length / 2 - 1; i >= 0; i--) {
adjustHeap(a, i, j);
}
//将堆顶元素与堆底互换
int temp = a[0];
a[0] = a[j - 1];
a[j - 1] = temp;
}
}
/**
* 构建大顶堆（升序）
* @param a 待处理的数组
* @param i 待处理非叶子节点
* @param length 待处理数组的长度
*/
private static void adjustHeap(int[] a, int i, int length) {
int temp = a[i];
for (int k = 2 * i + 1; k < length; k = 2 * i + 1) {
if (k + 1 < length && a[k] < a[k+1]) {
k++;
}
if (a[k] > temp) {
a[i] = a[k];
i = k;
} else {
//如果当前节点不大于索引节点，那么大顶堆已形成，因为是从下之上的
break;
}
}
a[i] = temp;
}
复制代码
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
