1.冒泡排序
1.概述
N个数字要排序完成，总共进行N-1趟排序，每i趟的排序次数为(N-i)次，所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数,每次都沉淀一个最大的数。
在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。
2.代码实现
定义一个布尔变量 hasChange，用来标记每轮是否进行了交换。在每轮遍历开始时，将 hasChange 设置为 false。若当轮没有发生交换，说明此时数组已经按照升序排列，hasChange 依然是为 false。此时外层循环直接退出，排序结束。
static void bubbleSorting(int[] arr) {
boolean hasChange = true;
for (int i = 0, n = arr.length; i < n && hasChange; i++) {
hasChange = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
hasChange = true;
}
}
}
}
3.算法分析
空间复杂度 O(1)、时间复杂度 O(n²)。
这是一个稳定的算法，稳定是指，两个相等的数，在排序过后，相对位置保持不变。
分情况讨论：
- 给定的数组按照顺序已经排好：只需要进行
n-1次比较，两两交换次数为 0，时间复杂度为 O(n)，这是最好的情况。 - 给定的数组按照逆序排列：需要进行
n*(n-1)/2次比较，时间复杂度为 O(n²)，这是最坏的情况。 - 给定的数组杂乱无章。在这种情况下，平均时间复杂度 O(n²)。
2.插入排序
1.概述
每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。
2. 代码实现
static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j <= i; j++) {
if (arr[i] < arr[j]) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
}
3. 算法分析
- 在冒泡排序中，经过每一轮的排序处理后，数组后端的数是排好序的。
- 在插入排序中，经过每一轮的排序处理后，数组前端的数是排好序的。
空间复杂度 O(1)，时间复杂度 O(n²)。
分情况讨论：
- 给定的数组按照顺序排好序：只需要进行 n-1 次比较，两两交换次数为 0，时间复杂度为 O(n)，这是最好的情况。
- 给定的数组按照逆序排列：需要进行
n*(n-1)/2次比较，时间复杂度为 O(n²)，这是最坏的情况。 - 给定的数组杂乱无章：在这种情况下，平均时间复杂度是 O(n²)。
因此，时间复杂度是 O(n²)，这也是一种稳定的排序算法。
4.优化插入排序
折半插入排序：向有序的序列中插入元素，那么插入位置可以不断的平分有序序列，并把待插入的元素的关键字与平分有序序列得到的关键字比较。以确定下一步要平分的子序列。直到找到合适的插入位置为止。找到插入位置后 从插入位置开始将数组整体右移到循环的位置。
static void binaryInsertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int left = 0;
int right = i; // 1
while (left < right) {
int mid = (left + right) >> 1; // 0
if (arr[i] <= arr[mid]) {
right = mid;
} else {
left = mid + 1;
}
}
int temp = arr[i];
//找到合适的插入位置，数组就从插入的位置开始移动
for (int j = i; j > left; j--) {
arr[j] = arr[j - 1];
}
arr[left] = temp;
}
}
时间复杂度O（nlogn） 空间复杂度O（1）
3.选择排序
1.概述
从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。
2.代码实现
static void selectSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int temp = arr[i];
int minIndex = i;
//找出剩余元素中最小的
for (int j = i; j < arr.length - 1; j++) {
if (arr[minIndex] > arr[j + 1]) {
minIndex = j + 1;
}
}
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
3.算法分析
空间复杂度 O(1)，时间复杂度 O(n²)。
那选择排序是稳定的排序算法吗？
答案是否定的，选择排序是一种不稳定的排序算法。选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。
比如 5，8，5，2，9 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以就不稳定了。正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。
4.希尔排序：
1. 概述
对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。
先将整个待排序的序列分割成若干个子序列，每个子序列由相差一定长度的数据元素组成（这个相差的长度称为增量），然后我们分别对这些子序列进行直接插入排序，一轮排序后再取第二个增量，以此类推，需要注意的是对于希尔排序中增量的确定没有统一的规定，通常的做法是：第一个增量为待排序序列长度的二分之一（取整），然后逐渐减半（取整），直到等于1为止。
增量怎么选：素数的比较好。最好用素数作为增量。
例如：
第一步：按照增量为3的进行分组，即1，4一组，2，5一组，3单独一组
第二步:增量为2，1，3一组，2，4一组，3，5一组
第三步：
2. 代码实现
static void shellSort(int[] arr) {
int increment = (arr.length >> 1);
for (int i = increment; i > 0; i--) { // 步长 >0
for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + i]) {
int temp = arr[j];
arr[j] = arr[i + j];
arr[i + j] = temp;
}
}
}
}
package com.wx.datastructure;
/*
希尔排序的思想：
先将整个待排序的序列分割成若干个子序列，每个子序列由相差一定长度的数据元素组成（这个相差的长度称为增量），
然后我们分别对这些子序列进行直接插入排序，一轮排序后再取第二个增量，
以此类推，需要注意的是对于希尔排序中增量的确定没有统一的规定，通常的做法是：
第一个增量为待排序序列长度的二分之一（取整），然后逐渐减半（取整），直到等于1为止。
*/
public class ShellSort {
public static void main(String[] args)
{
int[] data={2,6,4,3,9,5};
int len=data.length;
int temp;
//设置增量,增量是数据长度的一半依次减一减到一
for (int k=len/2;k>0;k--)
{
//将依据增量分割的序列进行对比
for(int i=k;i<len;i++)
{
if (data[i-k]>data[i])
{
//交换数据
temp=data[i-k];
data[i-k]=data[i];
data[i]=temp;
}
}
}
//输出
for(Integer x:data)
{
System.out.print(" "+x);
}
}
}
3.算法分析
时间复杂度：
希尔排序的时间性能取决于所取“增量”序列的函数，这涉及到一些数学上尚未解决的难题。但是有人通过大量的实验，给出了较好的结果：当 n 较大时，比较和移动的次数约在 n^1.25 到 (1.6n)^1.25 之间。所以可以这样简单记忆：
- 当 n 较小时，希尔排序和插入排序相差不大，都为 n² 左右。
- 当 n 很大时，时间增长幅度逐渐放缓，平均复杂度是 nlogn。
空间复杂度：O(1)。
5.归并排序
1.概述
归并排序的核心思想是分治，把一个复杂问题拆分成若干个子问题来求解。
归并排序的算法思想是：把数组从中间划分为两个子数组，一直递归地把子数组划分成更小的数组，直到子数组里面只有一个元素的时候开始排序。排序的方法就是按照大小顺序合并两个元素。接着依次按照递归的顺序返回，不断合并排好序的数组，直到把整个数组排好序。
2.代码实现
首先 将数组一分为二，然后将左半部分继续分，分到只有一个元素为止，代码就是
int mid = (low + high) >>> 1; mergeSort(arr, low, mid);
由于是递归，他会返回，返回时每层都达到条件low >= high，直接返回到最高层，此时左边部分分治结束，然后开始进行右边的分治
mergeSort(arr, mid + 1, high);
当右边以相同德方式分治完成后，low=high=mid=0;开始归并两个归并段。
是比较两个归并段的首位元素的大小，然后将其放入临时数组中，最后剩下的归并段的数据直接拷入临时数组。
最后将临时数组拷贝到原始数组，然后i一层层递归回去。
package com.wx.sort;
/**
* Created by wangxiang on 2022/2/22
*/
public class MergeSortWX {
public static void main(String[] args) {
int[] data = {7, 16, 23, 42, 30, 1, 9, 5, 6, 55, 2, 3, 3};
mergeSort(data, 0, data.length - 1);
}
static void mergeSort(int[] arr, int low, int high) {
//采用分治的思想，先分
if (low >= high) {
return;
}
int mid = (low + high) >>> 1;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
//分完之后就开始和，合并的条件就是
merge(arr, low, high, mid);
}
private static void merge(int[] arr, int low, int high, int mid) {
//将两个归并集合进行合并，首先需要保证的是归并集合钟有元素
int s1 = low; //第一个归并集合的起始序列
int s2 = mid + 1; //四二个归并集合的起始序列
//归并两个集合后的临时数组
int[] tempArr = new int[high - low + 1];
int i = 0;//临时数组的初始下标
//保证两个归并集合必须有元素才能合并
while (s1 <= mid && s2 <= high) {
//从两个归并集合的第一个元素开始比较，谁小谁排前面
if (arr[s1] >= arr[s2]) {
tempArr[i] = arr[s2];
//将小的拉下后小的归并段下标加1
s2++;
i++;
} else {
tempArr[i] = arr[s1];
s1++;
i++;
}
}
//当其中一个归并段先排完时，把剩下的归并段直接填到临时数组
while (s1 <= mid) {
tempArr[i] = arr[s1];
i++;
s1++;
}
while (s2 <= high) {
tempArr[i] = arr[s2];
i++;
s2++;
}
//最后一步就是将临时数组拷贝到原数组的位置
for (int j = low; j <= high; j++) {
arr[j] = tempArr[j - low];
}
}
}
3.算法分析
时间复杂度 O（nlogn）
空间复杂度 O（n）
稳定性：稳定
6.快速排序
1. 概述
快速排序也采用了分治的思想：把原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。
首先把数组中的一个数当做基准，一般会把数组中最左边的数当做基准base，从右边开始检索，找到比基准base小的数，然后从左边开始检索，找到比基准大的数之后停下，然后交换两个数的位置，继续检索，如果两边的检索相遇了，那么与基准数交换，这个时候数组就被分成了左右两个，然后递归继续排序左边的部分，完了之后递归排序右边的部分。
递归的终止条件就是low>high, 因为low是可以等于high的所以递归的终止条件就是low>high，然后开始循环检索，检索的终止条件是i==j，因为这个时候就要交换基准数，交换基准数之前，从右边检索，在i<j的条件下找到小于基准数的位置，从左边检索，在i<j的条件下找到大于基准数的位置。然后交换两个数。
如果i==j,交换基准数，然后递归处理左右两边
2.代码实现
package com.wx.sort;
/**
* Created by wangxiang on 2022/2/26
*/
public class QuickSort {
public static void main(String[] args) {
int[] data = {7, 16, 23, 42, 30, 1, 9, 5, 6, 55, 2, 3, 3};
int low = 0;
int high = data.length - 1;
quickSort(data, low, high);
}
static void quickSort(int[] arr, int low, int high) {
if (low > high) {
return;
}
//
int i = low;
int j = high;
int base = arr[i];
while (i != j) {
//从右开始检索，如果小于基准，则停下
while (arr[j] >= base && i < j) {
j--;
}
//从左往右检索，如果大于基准则停下
while (arr[i] <= base && i < j) {
i++;
}
//走到这里，说明low和high都停下了，交换两个的位置
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//走到这里说明两者相遇了，这个时候就要交换基准的位置
arr[low] = arr[i];
arr[i] = base;
//交换完基准以后数组被分为左右两边，递归处理左边
quickSort(arr, low, i - 1);
//递归处理右边
quickSort(arr, j + 1, high);
}
}
3.算法分析
快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下比较次数为 CN=2CN/2+N，复杂度为 O(NlogN)。
空间复杂度：logN
稳定性：不稳定
7.堆排序
1.概述
2.代码实现
3.算法分析