插入排序
插入排序思想：每趟将一个元素，按关键字大小插入到它前面已经排序的子序列中，依次重复，知直到插入全部元素。
插入排序分为直接插入排序、希尔排序、二分插入排序
直接插入排序
在第i趟排序过程中，key = arr[i]，arr[0]-arr[i-1]已经有序，从后往前依次将大于key的元素后移，直到遇到小于等于key的元素结束。
- 代码实现
/** * 直接插入排序，外层循环i代表待插入元素，内层循环j代表待比较元素*/
public static void straightInsert(int[] nums) {
int len = nums.length;
for (int i = 1; i < len; i++) {
int key = nums[i];
int j = 0;
for (j = i-1; j >= 0; j--) {
if (key < nums[j])
nums[j+1] = nums[j];
else {
break;
}
}
nums[j+1] = key;
}
}- 效率分析
- 时间复杂度O(n^2)，空间复杂度O(1)
- 稳定性分析
- 由于nums[j]>key是循环进行的判断条件，关键字相等的元素会相遇并进行比较，且排序前后顺序保持不变，所以 直接插入排序是稳定的
希尔排序
将一个数据序列分成若干组，每组由若干相隔一段距离增量的元素组成，在一个组内使用直接插入排序；增量通常设置为数据序列长度的一半，以后每次减半，直到为1。
- 代码实现
/** * 希尔排序，外层循环delt控制步长，中层循环i代表待插入元素，内层循环j代表待比较元素*/
public static void shellSort(int[] nums) {
int len = nums.length;
for (int delt = len / 2; delt > 0; delt /= 2) {
for (int i = delt; i < len; i++) {
int key = nums[i];
int j = 0;
for (j = i - delt; j >= 0; j -= delt) {
if (key < nums[j])
nums[j+delt] = nums[j];
else {
break;
}
}
nums[j+delt] = key;
}
}
}- 复杂度分析
- 时间复杂度O(n*(log(n))^2))，空间复杂度O(1)
- 稳定性分析
- 由于增量的存在，希尔排序过程中会错过相邻元素的比较，排序算法不稳定。
交换排序
交换排序分为冒泡排序和快速排序
冒泡排序
- 代码实现
/** * 冒泡排序(升序)，外层循环控制排序趟数，内层循环控制当前待比较元素*/
public static void bubbleSort(int[] nums) {
int len = nums.length;
for (int i = 1; i < len; i++) {
for (int j = 0; j < len - i; j++) {
if (nums[j] > nums[j+1]) {
int tmp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = tmp;
} else
continue;
}
}
}- 复杂度分析
- 时间复杂度O(n^2)，空间复杂度O(1)
- 稳定性分析
- 冒泡排序由于相邻元素一定会进行比较，且nums[j] > nums[j+1]作为判断条件，所以是稳定的
快速排序
- 代码实现
/** * 快速排序算法*/
public static void quickSort(int[] nums) {
quickSort(nums, 0, nums.length - 1);
}
private static void quickSort(int[] nums, int start, int end) {
if (0 <= start && start < end && end < nums.length) {
int front = start; // 初始头索引
int tail = end; // 初始尾索引
int key = nums[front]; // 选择当前序列的第一个元素为参考元素
while (front < tail) {
//从后向前，找到第一个小于参考元素的索引
while (nums[tail] >= key && front < tail) {
tail--;
}
//从后面找到了满足条件的元素
if (front < tail) {
nums[front++] = nums[tail]; // 移动后面的元素到前面，并更新头指针
}
//从前向后，找到第一个大于参考元素的索引
while (nums[front] <= key && front < tail) {
front++;
}
//找到了满足条件的元素
if (front < tail) {
nums[tail--] = nums[front]; // 移动前面的元素到后面，并更新尾指针
}
}
nums[front] = key;
quickSort(nums, start, front - 1);
quickSort(nums, tail + 1, end);
} else
return;
}- 复杂度分析
- 时间复杂度O(n*log(n))，空间复杂度O(log(n))
- 稳定性分析
- 快速排序算法是不稳定的
选择排序
选择排序包含直接选择排序和堆排序
直接选择排序
- 基本思想
- 第一趟从n个元素的数据中选择最小值，放在最前位置；下一趟从n-1个元素中选出最小值，放在次前位置。以此类推，经过n-1趟完成排序。
- 代码实现
/** * 直接选择排序*/
public static void straightSelect(int[] nums) {
int len = nums.length;
//外层循环趟数，每一趟确定一个最小值；内层循环代表待比较元素
for (int i = 0; i < len - 1; i++) {
int min = i; // 存放最小值索引
for (int j = i + 1; j < len; j++) {
if (nums[j] < nums[min])
min = j;
}
//交换
int tmp = nums[i];
nums[i] = nums[min];
nums[min] = tmp;
}
}- 复杂度分析
- 时间复杂度O(n^2)，空间复杂度O(1)
- 稳定性分析
- 直接选择排序会对不相邻的元素进行交换，所以是不稳定的
堆排序
- 代码实现
/** * 堆排序*/
public static void heapSort(int[] nums) {
int len = nums.length;
//创建最小堆
for (int parent = len / 2; parent >= 0; parent--) {
sift(nums, parent, len - 1);
}
//将根节点和最后一个节点交换位置，nums长度-1，然后再次调整堆
for (int i = len - 1; i > 0; i--) {
//将根节点与最后一个子节点交换
{
int tmp = nums[0];
nums[0] = nums[i];
nums[i] = tmp;
}
//重新调整堆
sift(nums, 0, i - 1);
}
}
private static void sift(int[] nums, int parent, int end) {
int child = parent * 2 + 1; //左孩子
int key = nums[parent]; //当前父节点元素
while (child <= end) { //当前节点存在子节点
//判断右孩子是否存在，若存在，child指向较小的孩子
if (child + 1 < end && nums[child + 1] < nums[child]) {
child++;
}
//判断父节点和当前孩子节点的大小关系
if (key > nums[child]) {
//孩子节点上移
nums[parent] = nums[child];
//父节点指针下移
parent = child;
//更新子节点
child = parent * 2 + 1;
} else {
break;
}
}
nums[parent] = key;
}- 复杂度分析
- 时间复杂度O(n*log(n))，空间复杂度O(1)
- 稳定性分析
- 堆排序不稳定
归并排序
归并排序分为自上而下和自下而上两种
自上而下
自上而下归并是一种递归的方法，分为两种操作：拆分操作、合并操作
- 代码实现
/** * 归并排序算法：自顶向下递归排序*/
public class MergeSort2 {
//合并操作，根据索引合并两个子序列
public static void merge2(int[] x, int start, int mid, int end) {
int[] tmp = new int[end - start + 1];
int index1 = start, index2 = mid + 1, index = 0;
while (index1 <= mid && index2 <= end) {
if (x[index1] < x[index2])
tmp[index++] = x[index1++];
else
tmp[index++] = x[index2++];
}
while (index1 <= mid)
tmp[index++] = x[index1++];
while (index2 <= end)
tmp[index++] = x[index2++];
//移动数组元素
for (int i = 0; i < tmp.length; i++)
x[start + i] = tmp[i];
}
//拆分排序
public static void sort2(int[] x, int start, int end) {
if (start < end) { //递归进行的条件
int mid = (start + end) / 2;
sort2(x, start, mid);
sort2(x, mid + 1, end);
merge2(x, start, mid, end);
}
}
public static void mergeSort2(int[] x) {
sort2(x, 0, x.length - 1);
}
}自下而上归并
- 代码实现
/** * 归并排序算法:自底向上归并*/
public class MergeSort {
//遍历当前数组
public static void printNums(int[] nums) {
int len = nums.length;
StringBuffer sb = new StringBuffer("(");
int index = 0;
for (index = 0; index < len - 1; index++)
sb.append(nums[index] + ",");
sb.append(nums[len - 1]);
sb.append(")\n");
System.out.println(sb.toString());
}
//一次归并，合并相邻的子序列
public static void merge(int[] x, int[] tmp, int begin1, int begin2, int n) {
int len = x.length;
int index1 = begin1, index2 = begin2, index = index1; //索引
while (index1 < begin1 + n && index2 < begin2 + n && index2 < len) {
if (x[index1] < x[index2])
tmp[index++] = x[index1++];
else
tmp[index++] = x[index2++];
}
while (index1 < begin1 + n && index1 < len)
tmp[index++] = x[index1++];
while (index2 < begin2 + n && index2 < len)
tmp[index++] = x[index2++];
}
//一趟归并，合并两两相邻的子序列
public static void mergePass(int[] x, int n) {
int len = x.length;
int[] tmp = new int[len]; //辅助数组
for (int begin = 0; begin < len; begin += 2*n) {
merge(x, tmp, begin, begin + n, n);
}
//移动数组元素
for (int index = 0; index < len; index++)
x[index] = tmp[index];
}
//归并排序
public static void mergeSort(int[] x) {
int len = x.length;
for (int n = 1; n < len; n *= 2) {
mergePass(x, n);
}
}
}- 复杂度分析
- 时间复杂度为O(n*log(n))，空间复杂度为O(n)
- 稳定性分析
- 归并排序相邻元素会进行比较，排序是稳定的。