1、冒泡排序
1.从头到尾遍历所有元素，如果当前元素大于下一个元素，则进行交换。以此类推，则最大的元素将会被放到数组的末尾。
2.数组总长度减少1，继续重复上一步操作，直到最外层循环的元素个数变成1则排序完成。
-
public static void bubbleSort(int[] arr) {
-
//1、所有元素的数量
-
for (
int i = arr.length -
1; i >
0; i--) {
-
//2、交换元素的过程
-
for (
int j =
0; j < i; j++) {
-
//3、设置交换元素的条件
-
if (arr[j] > arr[j +
1]) {
-
int temp = arr[j];
-
arr[j] = arr[j +
1];
-
arr[j +
1] = temp;
-
}
-
}
-
}
-
}
冒泡排序算法只需要常数数量的额外的空间，所以空间复杂度为O(1)；
当数组是顺序序列时，时间复杂度为O(N)；
当数组是倒序序列时，时间复杂度为O(N^2)；//通常认为的平均复杂度也是如此
冒泡排序是一种稳定的排序算法；
2、选择排序
1、假设第一个元素是最小的元素，不断和后面的元素进行比较，直到找出最小的元素的下标，赋值给minIndex；
2、如果minIndex和第一个元素的下标（i）不相同，那么就进行数据交换；
3、重复上述步骤
-
public static void selectionSort(int[] arr) {
-
//1、遍历所有元素
-
for (
int i =
0; i < arr.length; i++) {
-
//2、假设第一个元素就是数值最小的元素
-
int minIndex = i;
-
-
//3、使用当前的元素和其它所有元素做对比
-
for (
int j = i; j < arr.length; j++) {
-
//4、元素进行比较
-
if (arr[j] < arr[minIndex]) {
-
minIndex = j;
//如果发现arr[j]比arr[minIndex]要小，则下标赋值给最小索引，即把j赋值给minIndex
-
}
-
}
-
//4、最后进行真正的数据交换，而前面的步骤只是下标赋值
-
if (minIndex != i) {
//注意，一开始的minIndex是和i相等的，所以需要判断minIndex和i不相等的情况。
-
int temp = arr[i];
-
arr[i] = arr[minIndex];
-
arr[minIndex] = temp;
-
}
-
}
-
}
时间复杂度和空间复杂度和冒泡排序是相同的，但是数据交换的操作更少，性能会高于冒泡排序；
需要注意的是，选择排序在标准语法上，相同的元素也是需要交换的，因此是一种不稳定的排序算法；
如何解决它的不稳定性呢？个人认为是开辟一个新的数组，将元素放入新的数组而不是进行交换，这种做法显然会牺牲空间。
3、插入排序
1、插入第一个元素，并指定该元素为已排序部分。
2、然后插入第二个元素，在和第一个元素构成的区域进行排序。
3、重复上述步骤
-
public static void insertionSort(int[] arr) {
-
//1、循环插入元素
-
for (
int i =
0; i < arr.length; i++) {
//如果这一步是从左往右的，那么下一步数据比较就应该从右往左为佳
-
//如果同向比较，可能会造成位置错乱的问题
-
//2、遍历已经存在于数组的元素，并进行排序（类似冒泡）
-
for (
int j = i -
1; j >=
0; j--) {
//应该从右往左进行数据比较
-
//3、对元素数值进行交换操作
-
if (arr[j] > arr[j +
1]) {
-
int temp = arr[j];
-
arr[j] = arr[j +
1];
-
arr[j +
1] = temp;
-
}
-
}
-
}
-
}
时间复杂度和空间复杂度与上述两种排序算法都相同。
在有序部分元素和待插入元素相等的时候，待插入的元素将被放在前面，因而插入排序是稳定的。
4、希尔排序
1、将所有数据分成（array.length/2）组
2、循环遍历每个小组，并对其进行排序
3、把步长变为原先的二倍，重复上述操作
-
public static void shellSort(int[] arr) {
-
//1、记录一共有多少个组
-
int gap = arr.length /
2;
-
-
//声明一个变量，记录当前值
-
int current;
-
-
//2、循环遍历小组
-
while (gap >
0) {
-
//对小组中的数据进行插入排序
-
for (
int j = gap; j < arr.length; j++) {
-
current = arr[j];
//得到需要比较的数据
-
int preIndex = j - gap;
//得到小组内上一个数据的下标
-
//进行插入排序
-
while (preIndex >=
0 && current < arr[preIndex]) {
-
//数据交换
-
arr[preIndex + gap] = arr[preIndex];
-
preIndex -= gap;
-
}
-
arr[preIndex + gap] = current;
-
-
}
-
gap = gap /
2;
-
}
-
}
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。
——摘自百度百科
空间复杂度认为是O（1）或者O（N）
时间复杂度通常认为是O（N^1.3~N^2）；
5、快速排序
1、记录一个基准数字，选取未排序数组的第一个元素作为基准数字；
2、数组第一个元素的下标记作i，数组最后一个元素的下标记作j；
3、从左边开始找到比基准数字小的元素，从右边开始找到比基准数字大的元素，然后将这两个元素交换；
4、将基准数字进行调整，把基准数字和下标为i的元素进行交换，并且基准数字接下来不再参与排序；
5、递归执行上述操作
-
public static void quickSort(int[] arr, int left, int right) {
-
//设置递归推出条件
-
if (left > right) {
-
return;
-
}
-
//记录左边编号和右边编号
-
int i = left;
-
int j = right;
-
//记录基准数字
-
int base = arr[left];
-
-
//主要操作
-
while (i != j) {
-
//右侧编号查找数字
-
while (j > i && arr[j] >= base) {
-
j--;
-
}
-
//左侧编号查找数字
-
while (i < j && arr[i] <= base) {
-
i++;
-
}
-
//数字交换
-
if (i < j) {
-
int temp = arr[i];
-
arr[i] = arr[j];
-
arr[j] = temp;
-
}
-
}
-
-
//基准数字调整，即基准数字和i下标位置数字交换
-
arr[left] = arr[i];
-
arr[i] = base;
-
-
//i位置是基准数字，不再参与排序过程
-
//左侧数字进行二次分类
-
quickSort(arr, left, i -
1);
-
-
//右侧数字进行二次分类
-
quickSort(arr, i +
1, right);
-
}
快速排序是上面五种排序算法中效率较高的一种，空间复杂度为O（log N）
时间复杂度为O（N * log N）
转载：https://blog.csdn.net/qq_23481475/article/details/106888344