冒泡排序：
从第一个数开始往后比若比后面的数大则交换,依次两两比较直到把最大的数排到最右边,称为第一趟冒泡排序,在重复上述过程即可。
时间复杂度O(N^2), 最好时间复杂度O(N^2),最差时间复杂度O(N^2)，额外空间复杂度O(1),实现可以做到稳定性。
比如待排序列(651703):
第一趟排序:561703--->516703--->516073--->516037
第二趟排序:156037--->150637--->105637--->105367
第三趟排序:015367--->013567
代码实现：
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int end = arr.length - 1; end > 0; end--) {
for (int i = 0; i < end; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
选择排序:
每一次从待排序的数据元素中选取最小（或最大）的一个元素放在序列的起始位置,直到全部待排的数据元素排完。
时间复杂度O(N^2), 最好时间复杂度O(N^2),最差时间复杂度O(N^2)额外空间复杂度O（1）,不稳定,但链表实现可以做到稳定性。
代码实现:
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if(arr[i]>arr[j]) {
swap(arr, i, j);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
插入排序:
将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,过程类似整理扑克牌,算法适用于少量数据的排序。
时间复杂度O(N^2),最好时间复杂度O(N),最差时间复杂度O(N^2),额外空间复杂度O(1),实现可以做到稳定性。
代码实现:
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] < arr[j]) {
swap(arr, i, j);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
归并排序:
将已有序的子序列合并、得到完全有序的序列;即先使每个子序列有序,再使子序列段有序。
例如：待排数据 (10 4 6 3 8 2 5 7)-->(10 4 6 3 )(8 2 5 7)-->(10 4)(6 3)(8 2)(5 7)-->
(4 10)(3 6)(2 8)(5 7)--->(3-4-6-10)(2 5 7 8)--->(2 3 4 5 6 7 8 10)
时间复杂度O(NlogN),额外空间复杂度O(N),实现可以做到稳定性。
代码实现:
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
sortProcess(arr, 0, arr.length - 1);
}
//递归：父问题的处理正确从而保证子问题的处理正确
public static void sortProcess(int[] arr, int L, int R) {
if (L == R) {
return;
}
int mid = L + ((R - L) >> 1);
sortProcess(arr, L, mid);
sortProcess(arr, mid + 1, R);
merge(arr, L, mid, R);
}
//左右外排
public static void merge(int[] arr, int L, int m, int R) {
int[] help = new int[R - L + 1];
int i = 0;
int p1 = L;
int p2 = m + 1;
while (p1 <= m && p2 <= R) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= R) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
}
补充:判断流程的正确往往依赖OJ(Online Judge),但不一定每个案例都有对应的OJ检测 ，所以我们一般自己手撸一个对数器。
对数器：所以我们准备一个容易写不出错的版本(即一般直接暴力法写的版本)然后用代码生成随机样本，一个用自己写的优化的算法走,另一个跑一定对的版本如Java排序的Arrays.sort();然后进行把两种结果一起对比,则可用检查自己写的算法是否正确。
简易对数器代码:
public static void comparator(int[] arr) {
//暴力法一定对的方法,这里用的是java自带的排序方法
Arrays.sort(arr);}
//自定义产生待排序随机样本
public static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
// 分别传入用自己改进的排序算法和一定对的排序算法所返回的数组进行比对,若正确,则证明自己的优化版本算法可行
public static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
return false;
}
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1.length != arr2.length) {
return false;
}
for (int i = 0; i < arr1.length; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}