1、冒泡排序
分析：
7, 0, 6, 8, 1
相邻的两个数比较，交换，每次循环找出最大值。
第一次循环：
0, 7, 6, 8, 1
0, 6, 7, 8, 1
0, 6, 7, 1, 8
时间复杂度：O(n^2)，空间复杂度：O(1)
代码：
public static void bubbleSort(Integer[] nums) {
int len = nums.length;
while (len > 0) {
for (int i = 0; i < len - 1; i++) {
int next = i + 1;
if (nums[i] > nums[next]) {
int temp = nums[next];
nums[next] = nums[i];
nums[i] = temp;
}
}
len--;
}
}
2、快速排序
分析：
8,9,1,7,2,3,5,4,6,0
↑ ↑
8 9 1 7 2 3 5 4 6 0 基准点：8
<--
0 9 1 7 2 3 5 4 6 |0
-->
0 |9 1 7 2 3 5 4 6 9
0 6 1 7 2 3 5 4 |6 9
>>> 第一次分区可得
0 6 1 7 2 3 5 4 8 9
代码：
public static int partition(int[] arr, int left, int right) {
// 基准点
int pivot = arr[left];
while (left < right) {
// 从右往左移动，知道遇到小于pivot的元素
while (right > left && arr[right] >= pivot) {
right--;
}
arr[left] = arr[right];// 记录小于 pivot 的值
/* 再从左往右移动，直到遇见大于 pivot 的元素 */
while (left < right && arr[left] <= pivot) {
left++;
}
arr[right] = arr[left];// 记录大于 pivot 的值
}
arr[left] = pivot;// 记录基准元素到当前指针指向的区域
System.out.println(Arrays.toString(arr));
return left;// 返回基准元素的索引
}
public static void quickSort(int[] nums, int left, int right) {
if (left < right) {
int index = partition(nums, left, right);
// 基准元素左边递归
quickSort(nums, left, index - 1);
// 基准元素右边递归
quickSort(nums, index + 1, right);
}
}
3、选择排序
分析：
7, 0, 6, 8, 1
找出数组中的最小值，然后与第一位交换，然后再找出第二小的值与第二位交换
0 7 6 8 1
代码：
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIdx = i;
int min = arr[minIdx];
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < min) {
min = arr[j];
minIdx = j;
}
}
if (minIdx != i) {
arr[minIdx] = arr[i];
arr[i] = min;
}
}
}
4、堆排序
分析：
大根堆：每个节点的值都大于或者等于他的左右孩子节点的值
12
10 8
6 5 4 7
4 3 2 1
小根堆：每个结点的值都小于或等于其左孩子和右孩子结点的值
1
3 4
6 5 7 8
9 10
两种结构映射道数组：
大根堆：12 10 8 6 5 4 7 4 3 2
小根堆：1 3 4 6 5 7 8 9 10
排序思想：
1、将待排序得数据构造成一个大根堆，此时整个数组得最大值就是堆结构得顶端。
2、将顶端的数与末尾的数交换，此时末尾的数为最大值，剩余的待排序数组个数为n-1。
3、将剩余的n-1个数构造成大根堆，再将顶端数与n-1位置的数进行交换，如此反复执行，得到有序数组。
4 6 3 5 9
1、
4
6 3
5 9
对于[完全二叉树]，在填满的情况下（非叶子节点都有两个子节点），每一层的元素个数是上一层的2倍，根节点的数量是1。
所以最后一层的节点数量，一定是之前所有层的节点总数+1。
可以找到第一个叶子节点，为节点总数/2，即 arr.len / 2。
第一个非叶子节点的索引就是第一个叶子结点的索引-1，即arr.len / 2 -1。
对于填不满的二叉树[非完全二叉树]，这个计算方式仍然适用。
2、
4
|9 3
5 |6
3、找到下一个非叶子节点4，用它和它的左右子节点进行比较，4大于3，而4小于9，交换4和9位置
|9
|4 3
5 6
4、此时发现4小于5和6这两个子节点，我们需要进行调整，左右节点5和6中，6大于5且6大于父节点4，因此交换4和6的位置
9
|6 3
5 4
此时就构造出来一个大根堆,下来进行排序。
如此重复上述过程。
代码：
public static void adjustHeap(int[] arr, int i, int length) {
// 取出当前元素
int temp = arr[i]; // 这里即第一个非叶子节点的值
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {// 如果左子节点小于右子节点，则k指向右子节点
if (k + 1 < length && arr[k] < arr[k + 1]) {
k++;
}
if (arr[k] > temp) {
arr[i] = arr[k];
i = k;
} else {
break;
}
}
arr[i] = temp;// 将temp值放到最终的位置
}
public static void heapSort(int[] arr) {
// 1、构建大根堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
System.out.println("------");
// 2、调整堆结构+交换堆顶元素
for (int j = arr.length - 1; j > 0; j--) {
// 将堆顶的元素和末尾的元素进行交换
int temp = arr[0];
arr[0] = arr[j];
arr[j] = temp;
// 重新对堆进行调整
adjustHeap(arr, 0, j);
}
System.out.println(Arrays.toString(arr));
}
5、插入排序
分析：
7, 0, 6, 8, 1
↑
0, 7, 6, 8, 1
0, 6, 7, 8, 1
0, 1, 6, 7, 8
代码：
public static void insertSort(int[] arr) {
// 从第二个元素开始
for (int i = 0; i < arr.length; i++) {
int insertVal = arr[i];// 待插入的值
// 待插入数前一个数的下标
int insertIdx = i - 1;
while (insertIdx >= 0 && insertVal < arr[insertIdx]) {
arr[insertIdx + 1] = arr[insertIdx];
insertIdx--;// 为了找到插入的位置吗，不断向前遍历
}
// 把之前存起来的要插入的数插入到对应的位置
// insertIndex+1:顺序正确时，+1保持值不变 | 顺序不正确时（已经进了while循环减过1了）：+1后就是要插入的位置
arr[insertIdx + 1] = insertVal;
System.out.println(Arrays.toString(arr));
}
}
6、希尔排序
分析：
希尔排序和插入排序很相似，有点像插入排序的升级版本。
希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
|1, 4, 6, 3, |8, 9, 2, 23
代码：
// 希尔排序-插入法
public static void insertShellSort(int[] arr) {
int count = 1;//计数
// 分而治之，循环为每次总数除二
for (int i = arr.length / 2; i > 0; i /= 2) {
for (int j = i; j < arr.length; j++) {
int index = j;
int temp = arr[index];
// 比较每一组的值
if (arr[index] < arr[index - i]) {
// 如果后面的比前面的小，则将前面的数往后移
while (index - i > 0 && temp < arr[index - i]) {
arr[index] = arr[index - i];
index -= i;
}
arr[index] = temp;
}
}
System.out.println("希尔排序插入法第" + (count++) + "次排序后" + Arrays.toString(arr));
}
}
// 希尔排序交换法
public static void exchangeShellSort(int arr[]) {
int temp;// 临时数据
boolean flag = false;// 是否交换
int count = 1;
// 分而治之，将数组分组排序，i为步长
for (int i = arr.length / 2; i > 0; i /= 2) {
// 遍历分治的每一个分组
for (int j = i; j < arr.length; j++) {
// 遍历分治的每一个分组,的每一个值
for (int k = j - i; k >= 0; k -= i) {
if (arr[k + i] < arr[k]) {
// 交换
temp = arr[k + i];
arr[k + i] = arr[k];
arr[k] = temp;
flag = true;
}
if (!flag) {
break;
} else {
// 为了下次判断
flag = false;
}
}
}
System.out.println("希尔排序交换法第" + (count++) + "次排序后" + Arrays.toString(arr));
}
}
7、归并排序
代码：
public static int[] mergeSort(int[] sourceArray) throws Exception {
// 拷贝数组
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
if (arr.length < 2) {
return arr;
}
int middle = (int) Math.floor(arr.length / 2);
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
return merge(mergeSort(left), mergeSort(right));
}
protected static int[] merge(int[] left, int[] right) {
// 初始化新的数组
int[] result = new int[left.length + right.length];
int i = 0;
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}
评论