- // 冒泡排序
- // 时间复杂度为 O(N^2), 空间复杂度为 O(N)
- public class BubbleSort {
- public static void bubbleSort(int[] arr) {
- if (arr.length == 0 || arr.length == 1) {
- return;
- } else {
- // 随着每轮比较的进行, 都有一个大数沉到后面排好序, 因此外层的循环长度应该递减
- 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);
- }
- }
- }
- }
- }
- static void swap(int[] arr, int i, int j) {
- // 不利用第三个变量交换两变量的位置. 1.a 和同一个数异或运算两次得到 a 本身 2. 异或运算满足交换律
- arr[j] = arr[j] ^ arr[i];
- arr[i] = arr[j] ^ arr[i];
- arr[j] = arr[j] ^ arr[i];
- }
- public static void main(String[] args) {
- int[] a = {2, 1, 7, 10, 3, 9, 5, 4, 6, 8};
- bubbleSort(a);
- for(int i:a)
- System.out.print(i+",");
- }
- }
冒泡排序
插入排序:
- // 插入排序
- // 复杂度和数据状况有关系, 如果本来数组的有序性就比较好则复杂度低
- public class InsertSort {
- public static void insertSort(int[] arr) {
- if (arr == null || arr.length <2) {
- return;
- } else {
- for (int i = 1; i < arr.length; i++) {
- // 如果数组的有序性比较好, 如 1,2,3,4,5, 则 arr[j + 1] < arr[j] 这个条件可以使得比较提前终止,
- // 如果数组刚好是逆序的, 如 5,4,3,2,1, 则需要从 j 一直比较到 i=0;
- for (int j = i - 1; j>= 0 && arr[j + 1] <arr[j]; j--) {
- swap(arr, j, j + 1);
- }
- }
- }
- }
- static void swap(int[] arr, int i, int j) {
- arr[j] = arr[j] ^ arr[i];
- arr[i] = arr[j] ^ arr[i];
- arr[j] = arr[j] ^ arr[i];
- }
- public static void main(String[] args) {
- int[] a = {2, 1, 7, 10, 3, 9, 5, 4, 6, 8};
- insertSort(a);
- for (int i : a)
- System.out.print(i + ",");
- }
- }
插入排序
选择排序:
- // 选择排序
- // 时间复杂度为 O(N^2), 空间复杂度为 O(1)
- public class SelectionSort {
- public static void selectionSort(int[] arr) {
- if (arr == null || arr.length < 2) {
- return;
- } else {
- // 每轮都从未排序的数列中取出一个数, 将其与后面所有未排序的数作比较, 得到这些未排序数列里面的最小数, 将它换到已排好序数列的后面, 并扩大已排好序数列的范围.
- for (int i = 0; i < arr.length - 1; i++) {
- int minIndex = i;
- // i = 0 作为第一个已排序列
- for (int j = i + 1; j < arr.length; j++) {
- minIndex = arr[j] < arr[minIndex] ? j : minIndex;
- }
- swap(arr, i, minIndex);
- }
- }
- }
- static void swap(int[] arr, int i, int j) {
- // 此处不能用异或来完成交换, 因为如果 i=j, 两个相同的数异或等于 0,"arr[j] = arr[j] ^ arr[i]" 会将 arr[i] 和 arr[j] 同时置为 0, 这样就丢失了所有信息.
- // 如果 i 和 j 不相等, 但 a[i]==a[j] 是可以完成异或交换功能的, 因为 0 和任何数异或等于其本身
- // arr[j] = arr[j] ^ arr[i];
- // arr[i] = arr[j] ^ arr[i];
- // arr[j] = arr[j] ^ arr[i];
- int tmp = arr[i];
- arr[i] = arr[j];
- arr[j] = tmp;
- }
- public static void main(String[] args) {
- int[] a = {2, 1, 7, 10, 3, 9, 5, 4, 6, 8};
- selectionSort(a);
- for (int i : a)
- System.out.print(i + ",");
- }
- }
选择排序
归并排序:
- // 归并排序
- // 时间复杂度 O(NlogN), 空间复杂度 O(N)
- // 分治 + 外排的方法
- public class MergeSort {
- public static void mergeSort(int[] arr) {
- if (arr == null || arr.length < 2)
- return;
- else
- sortProcess(arr, 0, arr.length - 1);
- }
- private static void sortProcess(int[] arr, int L, int R) {
- if (L == R)
- return;
- else {
- int mid = L + ((R - L)>> 1);
- // 根据 Master 公式求其时间复杂度:
- sortProcess(arr, L, mid);//T(N/2)
- sortProcess(arr, mid + 1, R);//T(N/2)
- merge(arr, L, mid, R);//O(N)
- // 根据 Master 公式, 其时间复杂度为 T(N) = 2T(N/2)+O(N) = N*logN
- }
- }
- // 融合两个有序数组, 使之成为一个更大的有序数组的方法, 叫做外排
- private static void merge(int[] arr, int l, int mid, int r) {
- // 空间复杂度 O(体现在需要一个大小为数据量 N 的辅助数组 help 上)
- int[] help = new int[r - l + 1];
- int i = 0;
- int p1 = l;
- int p2 = mid + 1;
- while (p1 <= mid && p2 <= r)
- help[i++] = arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
- // 两个必有且只有一个越界
- while(p1<=mid)
- help[i++] = arr[p1++];
- while(p2<=r)
- help[i++] = arr[p2++];
- i = 0;
- while(l<=r)
- arr[l++] = help[i++];
- }
- public static void main(String[] args) {
- int[] a = {2, 1, 7, 10, 3, 9, 5, 4, 6, 8};
- mergeSort(a);
- for(int i:a)
- System.out.print(i+",");
- }
- }
- View Code
快速排序:
- import java.util.Arrays;
- // 快排
- // 时间复杂度最好为 O(NlogN). 数组逆序的时候最差, 时间复杂度为 O(N^2), 可以通过随机快排的方式使得其长期时间复杂度期望为 O(N*logN)
- // 空间复杂度最好为 O(logN), 数组逆序的时候最差, 空间复杂度为 O(N), 额外空间主要是每次 partition 函数返回的二元数组造成的.
- // 通过随机快排的方式使得其长期时间复杂度期望为 O(logN)
- // 所有递归函数都可以改为非递归版本, 因为递归的本质行为是系统在帮我们压栈. 改为非递归就是改成我们自己来压栈
- // 在工程上是不允许递归行为存在的, 因为递归过深可能会导致系统栈爆满, 系统不稳定. 因此工程上的快排都是非递归版本实现的.
- // 库函数都是高度优化过的
- public class QuickSort {
- static void quickSort(int[] arr, int L, int R) {
- if (L <R) {
- // 随机快排, 每次将中间随机一个数和数列最后一个元素交换位置, 放置逆序数列产生差的结果
- swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
- int[] p = partition(arr, L, R);
- quickSort(arr, L, p[0] - 1);
- quickSort(arr, p[1] + 1, R);
- }
- }
- static int[] partition(int[] arr, int L, int R) {
- int Less = L - 1;
- int more = R;
- int cur = L;
- // 以 arr[R] 作为基准, 有了随机快排, 这里的 arr[R] 被重新洗牌
- // 这里一次性处理了大于基准等于基准和小于基准的三种情况, 速度比传统快排要快
- while (cur < more) {
- if (arr[cur] < arr[R]) {
- // cur++, 因为换到 cur 位置上的一定是比基准 arr[R] 小的数, 直接将其扩到 Less 范围去, 且 cur 指向下一位置
- swap(arr, ++Less, cur++);
- } else if (arr[cur]> arr[R]) {
- // 交换到 cur 位置上的数大小位置, 交换过去的数一定大于基准 arr[R], 故 more--, 将其扩到 more 区域, 但 cur 位置不变
- swap(arr, --more, cur);
- } else {
- // 当前位置和基准 arr[R] 相等, 不扩到 Less 区域和 more 区域, 放在相等区域
- cur++;
- }
- }
- // 最后将基准交换到 more 区域的下一位置
- swap(arr, more, R);
- // 返回相等区域下标, 注意此时 more 位置上是交换过来的基准值, 不用加 1
- return new int[]{Less + 1, more};
- }
- static void swap(int[] arr, int i, int j) {
- int tmp = arr[i];
- arr[i] = arr[j];
- arr[j] = tmp;
- }
- public static void main(String[] args) {
- int a[] = {49, 38, 65, 97, 76, 13, 27, 49};
- quickSort(a, 0, a.length - 1);
- System.out.println(Arrays.toString(a));
- }
- }
快排
堆排序:
- import java.util.Arrays;
- // 堆排序
- // 堆是完全二叉树
- // 二叉树的底层可以用线性的结构来储存, 也就是说可以用数组来储存一个二叉树, 通过数组中下标的关系来表示这个堆. 设完全二叉树的一个节点在数组中的下标为 i,
- // 则其父节点的下标应该为 (i-1)/2, 其左孩子节点应该是 2*i+1, 其右孩子节点应该为 2*i+2
- public class HeapSort {
- static void heapSort(int[] arr) {
- if (arr == null || arr.length <2)
- return;
- else
- for (int i = 0; i < arr.length; i++)
- heapInsert(arr, i);
- int heapSize = arr.length;// 堆的大小等于数组的长度
- // 交换堆顶和最后一个元素
- swap(arr, 0, --heapSize);
- while (heapSize> 0) {
- heapify(arr, 0, heapSize);
- swap(arr, 0, --heapSize);
- }
- }
- static void heapInsert(int[] arr, int index) {
- while (arr[(index - 1) / 2] <arr[index]) {// 如果 index=0, -1/2=0 是根节点
- swap(arr, index, (index - 1) / 2);
- index = (index - 1) / 2;
- }
- }
- // 如果堆中有某个元素变小了, 将这个元素下沉以保持大根堆的过程 heapify
- static void heapify(int[] arr, int index, int heapSize) {
- int left = index * 2 + 1;// 在用数组存储的堆中, 节点 i 的左孩子节点是 2*i+1, 右节点是 2*i+2;
- // 这里 heapSize 是最后一个元素, 做堆排的时候, 因为是从堆顶交换来的最大值, 所以重新 heapify 要把它排除在外;
- while (left < heapSize) {
- int largest = left + 1 < heapSize && arr[left + 1]> arr[left] ? left + 1 : left;
- largest = arr[index]> arr[largest] ? index : largest;
- if (largest == index) {
- break;
- }
- swap(arr, largest, index);
- index = largest;
- left = index * 2 + 1;
- }
- }
- static void swap(int[] arr, int i, int j) {
- int tmp = arr[i];
- arr[i] = arr[j];
- arr[j] = tmp;
- }
- public static void main(String[] args) {
- int a[] = {49, 38, 65, 97, 76, 13, 27, 49};
- heapSort(a);
- System.out.println(Arrays.toString(a));
- }
- }
堆排序
希尔排序:
基数排序:
来源: http://www.bubuko.com/infodetail-2993339.html