插入排序
-
思想: 利用遍历数组，将第 i 位的值与前面一个数比较，如果 arr[i] 小于前面一个数则替换 arr[i]和arr[j] 的位置并重复再往前面比较直到大于或者等于前面的数
class InsertSort{ private static void insertSort(int[] arr){ // 遍历数组除0位以外所有元素 for (int i = 1; i < arr.length; i++){ // 对于第 i 个元素将其与前面的元素比较，如果小于则替换位置直到不小于 for (int j = i; j > 0; j--){ if (arr[j] < arr[j - 1]){ // 如果小于则交换位置，并且继续对比 swap(arr, j); } else { break; } } } } private static void swap(int[] arr, int j){ int tmp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = tmp; } }- 时间复杂度 O(n2), 空间复杂度O(1)
希尔排序
-
思想: 由于插入排序直接对源数据进行操作，对于数据本身非常乱的话，位置靠后的较小数据需要进行很多次对比才能移动到前面，希尔排序的核心是利用较大的数据跨度比较，将较小的数据经过较少的交换次数移动到前面
class shellSort{ public static void main(String[] args) { int[] arr = new int[]{11, 15, 1, 12, 2, 13, 3, 14, 4}; for (int gapNum = 4; gapNum > 0; gapNum >>= 1){ shellSort(arr, gapNum); } } private static void shellSort(int[] arr, int gapNum){ // 此处就是插入排序的做法 for (int i = gapNum; i < arr.length; i += gapNum){ for (int j = i; j > 0; j -= gapNum){ if (arr[j] < arr[j - gapNum]){ swap(arr, j, gapNum); } else { break; } } } System.out.println(Arrays.toString(arr)); } private static void swap(int[] arr, int j, int gapNum){ int tmp = arr[j]; arr[j] = arr[j - gapNum]; arr[j - gapNum] = tmp; } }- 优化点: 上面例子是 4 2 1 跨度的，最有序列应该是 knuth 序列 3n+1
- 时间复杂度O(n1.3)，空间复杂度O(1)
归并排序
单次归并排序
class Main{
public static void main(String[] args){
// 新建一个无序的 但是左右两部分分别有序的数组
int[] arr = new int[]{1, 3, 5, 7, 9, 2, 4, 6, 8};
// 调用merge方法。第一个参数是需要排序的数组,第二个参数是需要排序的起始位置,第三个参数是右边有序部分的第一个数的位置,第四个参数是需要排序部分的结束位置
merge(arr, 0, 5, 8);
}
static void merge(int[] arr, int left, int arrow, int right){
// 新建一个临时数组,接收需要排序的部分排序好的顺序
int[] tmpArray = new int[right - left + 1];
// 创建双指针,一个指向左边有序部分的第一个位置(left)， 另一个指向右边有序部分的第一个位置(arrow)
int i = left;
int j = arrow;
// 创建一个变量用于指向临时数据未填充部分的第一个位置
int k = 0;
// 对比arr[i]与arr[j]的值，较小的依次放在临时数组k的位置
while (i < arrow && j <= right){
// 因为i只需要遍历右边有序前面的所有数，所以 < arrow
// j需要遍历arrow到right里面所有的数据，所以 <= right
if (arr[i] <= arr[j]) {
tmpArray[k++] = arr[i++];
} else {
tmpArray[k++] = arr[j++];
}
}
// 一顿操作猛如虎，最终会以i到达arrow值结束或j到达right+1直接，且只有一个
// 所以需要判断一下哪一个没到达
while (i < arrow) tmpArray[k++] = arr[i++];
while (j <= right) tmpArray[k++] = arr[j++];
// 最终将tmp位置的值全部放入arr[left ... right]中
for (int m = 0; m < tmpArray.length; m++){
arr[left + m] = tmpArray[m];
}
}
}
迭代排序
- 二分法，取一半的一半…进行比较，直接取到1最终实现归并排序
class Main2 {
public static void main(String[] args) {
// 新建一个无序的 但是左右两部分分别有序的数组
int[] arr = new int[]{1, 3, 5, 7, 9, 2, 4, 6, 8};
// 调用merge方法。第一个参数是需要排序的数组,第二个参数是需要排序的起始位置,第三个参数是右边有序部分的第一个数的位置,第四个参数是需要排序部分的结束位置
sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
// 需要的是一个数组及排序的区间
static void sort(int[] arr, int left, int right) {
// 如果取到1个元素的数组，那么就不进行排序
if (left == right) return;
// 求出此区间的中值(防止溢出所以不是用(left + right)/2)
int mid = left + (right - left) / 2;
// 对左边进行排序(主要排序的对象还是2个元素的数组)
sort(arr, left, mid);
// 对右边进行排序
sort(arr, mid + 1, right);
//合并两边
merge(arr, left, mid + 1, right);
}
static void merge(int[] arr, int left, int arrow, int right) {
// 新建一个临时数组,接收需要排序的部分排序好的顺序
int[] tmpArray = new int[right - left + 1];
// 创建双指针,一个指向左边有序部分的第一个位置(left)， 另一个指向右边有序部分的第一个位置(arrow)
int i = left;
int j = arrow;
// 创建一个变量用于指向临时数据未填充部分的第一个位置
int k = 0;
// 对比arr[i]与arr[j]的值，较小的依次放在临时数组k的位置
while (i < arrow && j <= right) {
// 因为i只需要遍历右边有序前面的所有数，所以 < arrow
// j需要遍历arrow到right里面所有的数据，所以 <= right
if (arr[i] <= arr[j]) {
tmpArray[k++] = arr[i++];
} else {
tmpArray[k++] = arr[j++];
}
}
// 一顿操作猛如虎，最终会以i到达arrow值结束或j到达right+1直接，且只有一个
// 所以需要判断一下哪一个没到达
while (i < arrow) tmpArray[k++] = arr[i++];
while (j <= right) tmpArray[k++] = arr[j++];
// 最终将tmp位置的值全部放入arr[left ... right]中
for (int m = 0; m < tmpArray.length; m++) {
arr[left + m] = tmpArray[m];
}
}
}
- 时间复杂度O(nlogn),空间复杂度O(n)
快速排序
快排核心
public class QuickSort2 {
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 2, 4, 6, 8};
sort(arr);
System.out.println(Arrays.toString(arr));
}
static void sort(int[] arr){
// 确定一个基准，这个基准决定了前面部分的元素都小于等于这个基准，后面部分的元素都大于这个基准
int pivot = arr[arr.length - 1];
// 左指针指向数组的第一个位置
int left = 0;
// 右指针指向数组基准前面一个位置
int right = arr.length - 2;
// 循环开始，左指针左移到第一个大于基准的元素，右指针右移到第一个小于等于基准的元素
while (left <= right){
// 这里是 <= 会导致移动过程中 左指针超过右指针
while (left <= right && arr[left] <= pivot) left++;
while (left <= right && arr[right] > pivot) right--;
if (left < right) swap(arr, left, right);
}
// 最后把轴与left值交换
// 因为此时必然有left指向大数区第一个数组,right指向小数区最后一个数据
swap(arr, left, arr.length - 1);
}
static void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
迭代算法
public class QuickSort2 {
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 2, 4, 6, 8};
midSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
static void midSort(int[] arr, int left, int right){
// 首先判断是否只有一个元素，如果是，那就不用判断了
if (left >= right) return;
// 获取一次排序的基准轴
int mid = sort(arr, left, right);
// 对左半部分再次排序
midSort(arr, left, mid - 1);
// 对右半部分再次排序
midSort(arr, mid + 1, right);
}
static int sort(int[] arr, int leftBonud, int rightBound){
// 确定一个基准，这个基准决定了前面部分的元素都小于等于这个基准，后面部分的元素都大于这个基准
int pivot = arr[rightBound];
// 左指针指向需要排序的第一个位置
int left = leftBonud;
// 右指针指向基准前面一个位置
int right = rightBound - 1;
// 循环开始，左指针左移到第一个大于基准的元素，右指针右移到第一个小于等于基准的元素
while (left <= right){
// 这里是 <= 会导致移动过程中 左指针超过右指针
while (left <= right && arr[left] <= pivot) left++;
while (left <= right && arr[right] > pivot) right--;
if (left < right) swap(arr, left, right);
}
// 最后把轴与left值交换
// 因为此时必然有left指向大数区第一个数组,right指向小数区最后一个数据
swap(arr, left, rightBound);
return left;
}
static void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
- 时间复杂度 O(nlogn) 空间复杂度O(n)
小结: 快排和归并，两者区别在于。在迭代方式上，归并需要前一步处理好的数据，而快排是处理好数据给下一步
归并的核心是将排序好的数据按顺序放在一起，而快排只要将轴两边的数据放在前后就好了