排序算法的一些复习笔记。
顺便分享一个视频，群魔乱舞到秩序与整洁的变化挺爽的（小心精神污染）：15 Sorting Algorithms in 6 Minutes - YouTube
冒泡排序
维基百科：
重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 冒泡排序对n个项目需要O(n^2)的比较次数，且可以原地排序。
演示：
代码：
package bubble;
import java.util.Random;
/**
* @author Boli Tao
*/
public class BubbleSort {
/**
* 交换 arr 数组中索引为 index1 和 index2 的值
*
* @param arr array
* @param index1 index1
* @param index2 index2
*/
public static void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
/**
* bubble sort
*
* @param arr the array to be sorted
*/
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
public static void main(String[] args) {
Random random = new Random();
int[] array = new int[100000];
for (int i = 0; i < array.length; i++) {
array[i] = random.nextInt(Integer.MAX_VALUE);
}
bubbleSort(array);
for (int i = 0; i < array.length - 1; i++) {
if (array[i + 1] < array[i]) {
throw new IllegalArgumentException("冒泡排序写错了");
}
}
System.out.println("Test complete.");
}
}
选择排序
冒泡排序比较的是相邻元素，而选择排序是比较整体，并且选择排序交换的是最小值和未经排序“头部”元素。其时间复杂度为 O(n^2)。
演示：
代码：
package selection;
/**
* @author Boli Tao
*/
public class SelectionSort {
/**
* 交换 arr 数组中索引为 index1 和 index2 的值
*
* @param arr array
* @param index1 index1
* @param index2 index2
*/
private static void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
swap(arr, i, min_idx);
}
}
public static void main(String[] args) {
int[] arr = {37, 18, 7, 5, 24, 46, 28, 35, 11, 13, 2};
selectionSort(arr);
System.out.print("Sorted array:\n[");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if (i != arr.length - 1) {
System.out.print(" ,");
}
}
System.out.print("]");
}
}
插入排序
插入排序通过找到合适位置进行插入达到排序目的。时间复杂度为 O(n^2)。
演示：
代码：
package insertion;
/**
* @author Boli Tao
*/
public class InsertionSort {
static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// 后移
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
// 插入
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {37, 18, 7, 5, 24, 46, 28, 35, 11, 13, 2};
insertionSort(arr);
StringBuilder builder = new StringBuilder();
builder.append("Sorted array:\n[");
for (int i = 0; i < arr.length; i++) {
builder.append(arr[i]);
if (i != arr.length - 1) {
builder.append(" ,");
}
}
builder.append("]");
System.out.println(builder.toString());
}
}
归并排序
空间复杂度 O(n)，时间复杂度 O(nlogn)。
演示：
package merge;
/**
* @author 陶波利
*/
public class MergeSort {
private static void merge(int[] arr, int l, int m, int r) {
int leftArraySize = m - l + 1;
// r - (m + 1) + 1
int rightArraySize = r - m;
// temp array
int[] leftTempArray = new int[leftArraySize];
int[] rightTempArray = new int[rightArraySize];
// 把 arr 中的数据拷入两个 temp 数组
for (int i = 0; i < leftArraySize; i++) {
leftTempArray[i] = arr[l + i];
}
for (int i = 0; i < rightArraySize; i++) {
rightTempArray[i] = arr[m + 1 + i];
}
// 两个 temp 数组的索引
int i = 0, j = 0;
// arr 数组的索引
int k = l;
// 将 temp 数组的数据按顺序填入 arr
while (i < leftArraySize && j < rightArraySize) {
if (leftTempArray[i] <= rightTempArray[j]) {
arr[k] = leftTempArray[i];
i++;
} else {
arr[k] = rightTempArray[j];
j++;
}
k++;
}
while (i < leftArraySize) {
arr[k] = leftTempArray[i];
i++;
k++;
}
while (j < rightArraySize) {
arr[k] = rightTempArray[j];
j++;
k++;
}
}
public static void mergeSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
public static void main(String[] args) {
int[] arr = {37, 18, 7, 5, 24, 46, 28, 35, 11, 13, 2};
mergeSort(arr, 0, arr.length - 1);
StringBuilder builder = new StringBuilder();
builder.append("Sorted array:\n[");
for (int i = 0; i < arr.length; i++) {
builder.append(arr[i]);
if (i != arr.length - 1) {
builder.append(" ,");
}
}
builder.append("]");
System.out.println(builder.toString());
}
}
快速排序
快速排序相比冒泡排序，不是比较相邻元素，而是比较和交换大数和小数，做到把小数浮到上面、大数沉到下面。
快速排序不稳定，平均时间复杂度为 O(nlogn)。
演示：
代码：
package quick;
import java.util.Random;
/**
* @author 陶波利
*/
public class QuickSort {
/**
* 交换 arr 数组中索引为 index1 和 index2 的值
*
* @param arr array
* @param index1 index1
* @param index2 index2
*/
private static void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
int pivotIndex = left;
while (left < right) {
// 从右侧开始寻找比基准数小的元素的索引
while (left < right && arr[right] >= pivot) {
right--;
}
//从左侧开始寻找比基准数大的元素的索引
while (left < right && arr[left] <= pivot) {
left++;
}
// 把大数移到右边，小数移到左边
swap(arr, left, right);
}
// 把 pivot 移到中间
swap(arr, pivotIndex, left);
return left;
}
private static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int pi = partition(arr, left, right);
quickSort(arr, left, pi - 1);
quickSort(arr, pi + 1, right);
}
public static void sort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
public static void main(String[] args) {
Random random = new Random();
int[] array = new int[1000000];
for (int i = 0; i < array.length; i++) {
array[i] = random.nextInt(Integer.MAX_VALUE);
}
sort(array);
for (int i = 0; i < array.length - 1; i++) {
if (array[i + 1] < array[i]) {
throw new IllegalArgumentException("快排写错了");
}
}
}
}
堆排序
平均时间复杂度为 O(nlogn)。
自己实现一个最大堆，所有的问题都迎刃而解。
代码：
package heap;
import array.Array;
import java.util.Random;
/**
* @author 陶波利
*/
public class MaxHeap<E extends Comparable<E>> {
private Array<E> data;
public MaxHeap(int capacity) {
data = new Array<>(capacity);
}
public MaxHeap() {
data = new Array<>();
}
/**
* 构造函数：将传入数组组成为最大堆
*
* @param arr 待化为最大堆的数组
*/
public MaxHeap(E[] arr) {
data = new Array<>(arr);
for (int i = parent(arr.length - 1); i >= 0; i--) {
siftDown(i);
}
}
public int size() {
return data.getSize();
}
public boolean isEmpty() {
return data.isEmpty();
}
/**
* @param index index
* @return index 的父节点的索引
*/
private int parent(int index) {
if (index == 0) {
throw new IllegalArgumentException("index 0 doesn't have parent.");
}
return (index - 1) / 2;
}
private int leftChild(int index) {
return index * 2 + 1;
}
private int rightChild(int index) {
return index * 2 + 2;
}
/**
* 向堆中添加元素
*
* @param e 待添加的元素值
*/
public void add(E e) {
data.addLast(e);
siftUp(data.getSize() - 1);
}
/**
* 为满足最大堆性质而设计的元素上浮方法
*
* @param k 需要被上浮的元素索引
*/
private void siftUp(int k) {
while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
data.swap(k, parent(k));
k = parent(k);
}
}
/**
* 取出堆中最大元素
*
* @return
*/
public E extractMax() {
E ret = getMax();
data.swap(0, data.getSize() - 1);
data.removeLast();
siftDown(0);
return ret;
}
public E getMax() {
if (data.getSize() == 0) {
throw new IllegalArgumentException("Size is 0, no element in heap.");
}
return data.get(0);
}
/**
* 为满足最大堆性质而设计的元素下沉方法
* TODO: 需要进一步理解
*
* @param k 需要被下沉的元素索引
*/
private void siftDown(int k) {
while (leftChild(k) < data.getSize()) {
int j = leftChild(k);
if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
j = rightChild(k);
}
// ↑此时 j 表示孩子节点中更大元素的索引
if (data.get(k).compareTo(data.get(j)) > 0) {
break;
}
data.swap(k, j);
k = j;
}
}
public E replace(E e) {
E ret = getMax();
data.set(0, e);
siftDown(0);
return ret;
}
/**
* 测试类
*
* @param args args
*/
public static void main(String[] args) {
int n = 1000000;
MaxHeap<Integer> maxHeap = new MaxHeap<>();
Random random = new Random();
for (int i = 0; i < n; i++) {
maxHeap.add(random.nextInt(Integer.MAX_VALUE));
}
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = maxHeap.extractMax();
}
for (int i = 1; i < n; i++) {
if (arr[i - 1] < arr[i]) {
throw new IllegalArgumentException("Error: 最大堆实现出现问题！");
}
}
System.out.println("Completed!");
}
}
自定义的 Array 类如下：
package array;
/**
* 自定义的 Array 类
*
* @author 陶波利
*/
public class Array<E> {
private E[] data;
private int size;
public Array() {
this(10);
}
public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}
public Array(E[] arr) {
data = (E[]) new Object[arr.length];
for (int i = 0; i < arr.length; i++) {
data[i] = arr[i];
}
size = arr.length;
}
public int getSize() {
return size;
}
public int getCapacity() {
return data.length;
}
public boolean isEmpty() {
return size == 0;
}
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get() failed, index is illegal.");
}
return data[index];
}
public void set(int index, E value) {
data[index] = value;
}
public boolean isContaianed(E value) {
for (E m : data) {
if (value.equals(m)) {
return true;
}
}
return false;
}
public int find(E value) {
for (int i = 0; i < data.length; i++) {
if (value.equals(data[i])) {
return i;
}
}
return -1;
}
public void add(int index, E value) {
// if (size >= data.length) {
// throw new IllegalArgumentException("add() method failed, array is full.");
// }
if (index < 0 || index > size) {
throw new IllegalArgumentException("add() failed. Requirement: 0 <=index <= size.");
}
if (size == data.length) {
resize(2 * data.length);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = value;
size++;
}
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
public void addFirst(E value) {
add(0, value);
}
public void addLast(E value) {
add(size, value);
}
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("remove() failed, index is illegal.");
}
E removedValue = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--;
// loitering objects != memory leak
data[size] = null;
if (size == data.length / 4 && data.length / 2 != 0) {
// TODO: / 4?
resize(data.length / 2);
}
return removedValue;
}
public E removeFirst() {
return remove(0);
}
public E removeLast() {
return remove(size - 1);
}
public void removeElement(E value) {
int index = find(value);
if (-1 != index) {
remove(index);
}
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
builder.append("[");
for (int i = 0; i < size; i++) {
builder.append(data[i]);
if (i != size - 1) {
builder.append(", ");
}
}
builder.append("]");
return builder.toString();
}
public E getLast() {
return get(size - 1);
}
public E getFirst() {
return get(0);
}
/**
* 交换索引为 i j 的元素
*
* @param i index i
* @param j index j
*/
public void swap(int i, int j) {
if (i < 0 || i >= size || j < 0 || j >= size) {
throw new IllegalArgumentException("Index is illegal");
}
E temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
希尔排序
package shell;
import java.util.Random;
/**
* @author 陶波利
*/
public class ShellSort {
private static void shellInsert(int[] arr, int d) {
for (int i = d; i < arr.length; i++) {
int j = i - d;
//记录要插入的数据
int temp = arr[i];
//从后向前，找到比其小的数的位置
while (j >= 0 && arr[j] > temp) {
//向后挪动
arr[j + d] = arr[j];
j -= d;
}
//存在比其小的数
if (j != i - d) {
arr[j + d] = temp;
}
}
}
public static void shellSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
int d = arr.length / 2;
while (d >= 1) {
shellInsert(arr, d);
d /= 2;
}
}
public static void main(String[] args) {
Random random = new Random();
int[] array = new int[1000000];
for (int i = 0; i < array.length; i++) {
array[i] = random.nextInt(Integer.MAX_VALUE);
}
shellSort(array);
for (int i = 0; i < array.length - 1; i++) {
if (array[i + 1] < array[i]) {
throw new IllegalArgumentException("希尔排序写错了");
}
}
System.out.println("Test complete.");
}
}
参考： Sorting Algorithms - GeeksforGeeks francistao/LearningNotes: Enjoy Learning. VisuAlgo - visualising data structures and algorithms through animation 排序算法 - 维基百科，自由的百科全书