插入排序
从数组的第二个数开始把每个数插入到前面
插入的时候需要遍历前面的数组找到正确的插入位置，使得插入后前面的数组仍是有序的
import java.util.Arrays;
/**
* @Author Redarm
* @Date 2020/7/21 6:26 下午
**/
public class InsertSort {
public static void main(String[] args) {
int[] a = {0,1,1,2,10,4,9,5,49,30,30};
sort(a);
Arrays.stream(a).forEach(it -> System.out.println(it));
}
// 从小到大排序
public static void sort(int[] array){
// 从第二个数开始循环遍历
for (int i = 1; i < array.length; i++){
// 要插入的数
int flag = array[i];
// 遍历这个要插入的数前面的所有数，找到要插入的位置
for (int j = i-1; j >= 0; j--){
// 如果这个数比要插入的数大，说明要插入的位置在前面，把这个数向后移动一位
if (array[j] > flag) {
array[j+1] = array[j];
} else { // 如果这个数比要插入的数小或者等于要插入的数，说明要插入的位置是这个数的后面，然后结束循环
array[j+1] = flag;
break;
}
}
}
}
}
- 平均复杂度为O(n²)
- 最坏时间复杂度：O(n²)
- 空间复杂度：O(1)
快排
在数组中找一个基数，把比基数大的都放到右面，比基数小的放到左面，基数放到中间
从右面开始找可以保证最后左右引用指向同一个数的时候这个数比基数小
选最左面的数为基数，然后最后指向的数放到最左面，基数放到中间
package cn.redarm;
import java.util.Arrays;
import java.util.Random;
public class QuickSort {
public static void main(String[] args) {
Random random = new Random(1);
int[] array = new int[1000];
for (int i=0; i< array.length; i++)
array[i] = random.nextInt(1000 );
quickSort(array);
Arrays.stream(array).forEach(it -> System.out.print(it + " "));
}
public static void quickSort(int[] array){
sort(array, 0, array.length-1);
}
private static void sort(int[] array, int start, int end){
if (start >= end)
return;
int left = start;
int right = end;
int key = array[left];
int temp;
while (left < right){
// 找出右面比基数小的值
while (left < right && array[right] >= key)
right--;
// 找出左面比基数大的值
while (left < right && array[left] <= key)
left ++;
// 交换
temp = array[left];
array[left] = array[right];
array[right] = temp;
}
// 因为是从右面开始找比基数小的值，所以最后左右指向同一个数array[left]一定是比基数小的
// 放到数组最左面，然后数组的中间位置array[left]放基数
array[start] = array[left];
array[left] = key;
// 左右两面递归快排
sort(array, start, left-1);
sort(array, left+1, end);
}
}
归并排序
经典的分治思想，把数组从中间分开，然后对左右的两个数组再进行分割，直到分成一个数，然后进行合并，每两个数组进行合并的时候，如果这两个数组是只有一个元素，那么就是小的在前打的在后，如果这两个数组是具有多个元素，那这两个数组肯定是排好序的，第一个数字一定是最小的，只需要两个指针指向第一个数字，比较第一个数字最小的放到新的数组中，然后指针后移继续比较这组的第二个和另一组的第一个数，把两个数组合并到一个数组。
package com.company.sort;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
public class Sort {
public static void main(String[] args) {
int[] array = new int[9999];
Random random = new Random(1);
for (int i=0; i< array.length; i++)
array[i] = random.nextInt(9999);
array = sort(array);
Arrays.stream(array).forEach(it -> System.out.print(it + " "));
}
private static int[] sort(int[] array){
if (array.length <=1)
return array;
int mid = array.length / 2;
int[] left = sort(Arrays.copyOfRange(array, 0 ,mid));
int[] right = sort(Arrays.copyOfRange(array, mid, array.length));
return merge(left, right);
}
private static int[] merge(int[] left, int[] right){
int l = 0;
int r = 0;
ArrayList<Integer> list = new ArrayList<>();
while (l < left.length && r < right.length){
if (left[l] <= right[r])
list.add(left[l++]);
else
list.add(right[r++]);
}
if (l <= left.length){
for (int i=r; i< right.length; i++)
list.add(right[i]);
}
if (r <= right.length){
for (int i=l; i< left.length; i++)
list.add(left[i]);
}
int[] array = new int[list.size()];
for (int i=0; i<list.size(); i++)
array[i] = list.get(i);
return array;
}
}