冒泡排序(稳定)
- 原理:两两交换,直到把最大的数交换至最后,总共需要循环 len(list) - 1 次
- 代码:
public class BubbleSort {
public static void sort(int[] array) {
if (array == null || array.length == 0) {
return;
}
int length = array.length;
//外层:需要length-1次循环比较
for (int i = 0; i < length - 1; i++) {
//内层:每次循环需要两两比较的次数,每次比较后,都会将当前最大的数放到最后位置,所以每次比较次数递减一次
for (int j = 0; j < length - 1 - i; j++) {
if (array[j] > array[j+1]) {
//交换数组array的j和j+1位置的数据
swap(array, j, j+1);
}
}
}
}
/**
* 交换数组array的i和j位置的数据
* @param array 数组
* @param i 下标i
* @param j 下标j
*/
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
插入排序(稳定)
- 原理:类似扑克牌,前半部分是已排好序的列表,后半部分依次插入前半部分
- 代码:
public class InsertSort {
public static void sort(int[] a) {
if (a == null || a.length == 0) {
return;
}
for (int i = 1; i < a.length; i++) {
int j = i - 1;
int temp = a[i]; // 先取出待插入数据保存,因为向后移位过程中会把覆盖掉待插入数
while (j >= 0 && a[j] > temp) { // 如果待是比待插入数据大,就后移
a[j+1] = a[j];
j--;
}
a[j+1] = temp; // 找到比待插入数据小的位置,将待插入数据插入
}
// 另一种写法
for (int i = 1; i < listSize; i++) {
for (int j = 0; j < i; j++) {
if (numList.get(i) < numList.get(j)) {
numList.add(j, numList.get(i));
numList.remove(i+1);
}
}
}
}
}
选择排序(不稳定)
- 原理:每一次循环,都选择未排好列表中最小的一项放到前面
- 代码:
public class SelectSort {
public static void sort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i+1; j < arr.length; j ++) { //选出之后待排序中值最小的位置
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
}
希尔排序
- 原理:对当前 gap 下的列表进行插入排序,不断缩小 gap 直到为1
- 代码:
//优化前
for (gap = n / 2; gap > 0; gap /= 2) //步长
for (i = 0; i < gap; i++) //直接插入排序
for (j = i + gap; j < n; j += gap)
//插入排序
//优化后
public class ShellSort {
public static void sort(int[] arr) {
int gap = arr.length / 2;
for (;gap >= 1; gap = gap/2) { //不断缩小gap,直到1为止
for(int i = gap; i < arr.length; i++) { //使用当前gap进行组内插入排序
int j = i - gap;
int temp = a[i];
while(j >= 0 && a[j] > temp) {
a[j+gap] = a[j];
j -= gap;
}
a[j+gap] = temp;
}
}
}
}
快速排序(不稳定)
- 原理:
- 从数列中取出一个数作为 pivot
- 将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边
- 对左右区间重复第二步,直到区间只有一个数
- 非递归:用栈存储左右下标
- 代码:
public class QuickSort {
/**
* 快速排序(左右指针法)
* @param arr 待排序数组
* @param low 左边界
* @param high 右边界
*/
public static void sort2(int arr[], int low, int high) {
if (arr == null || arr.length <= 0) {
return;
}
if (low >= high) {
return;
}
int left = low;
int right = high;
int key = arr[left];
while (left < right) {
while (left < right && arr[right] >= key) {
right--;
}
while (left < right && arr[left] <= key) {
left++;
}
if (left < right) {
swap(arr, left, right);
}
}
swap(arr, low, left);
System.out.println("Sorting: " + Arrays.toString(arr));
sort2(arr, low, left - 1);
sort2(arr, left + 1, high);
}
public static void swap(int arr[], int low, int high) {
int tmp = arr[low];
arr[low] = arr[high];
arr[high] = tmp;
}
}
归并排序(稳定)
- 原理:将列表均分成两部分分别排序,然后 merge 两个有序列表
- 代码:
public class MergeSort {
public static int[] sort(int [] a) {
if (a.length <= 1) {
return a;
}
int num = a.length >> 1;
int[] left = Arrays.copyOfRange(a, 0, num);
int[] right = Arrays.copyOfRange(a, num, a.length);
return mergeTwoArray(sort(left), sort(right));
}
public static int[] mergeTwoArray(int[] a, int[] b) {
int i = 0, j = 0, k = 0;
int[] result = new int[a.length + b.length]; // 申请额外空间保存归并之后数据
while (i < a.length && j < b.length) { //选取两个序列中的较小值放入新数组
if (a[i] <= b[j]) {
result[k++] = a[i++];
} else {
result[k++] = b[j++];
}
}
while (i < a.length) { //序列a中多余的元素移入新数组
result[k++] = a[i++];
}
while (j < b.length) {//序列b中多余的元素移入新数组
result[k++] = b[j++];
}
return result;
}
public static void main(String[] args) {
int[] b = {3, 1, 5, 4};
System.out.println(Arrays.toString(sort(b)));
}
}
堆排序
- 原理:
- 构建一个大(小)根堆
- 循环,每次堆顶就是最大值,把堆顶换到最后再重新“堆”化
- 代码:
class HeapSort {
private int[] nums = {12, 6, 4, 9, 1, 5, 14, 3};
public void swap(int[] arr, int i, int j) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
// 构造大根堆
public int[] buildHeap() {
// 变为下标从 1 开始的数组,方便计算
int[] arr = new int[nums.length + 1];
System.arraycopy(nums, 0, arr, 1, nums.length);
// 下标从 1 开始的话,最后一个非叶子节点的下标是 i/2
// 叶子节点是不需要堆化的
for (int i = nums.length / 2; i > 0; i--) {
heapify(arr, i, nums.length);
}
return arr;
}
// 将以下标 index 为根的二叉树进行堆化,len 表示数组总长度
public void heapify(int[] arr, int index, int len) {
while (true) {
int left = index * 2;
int right = left + 1;
int maxIndex = index;
// 下标 index(根), left(左子), right(右子), 看谁最大
if (left <= len && arr[left] > arr[index]) {
maxIndex = left;
}
if (right <= len && arr[right] > arr[maxIndex]) {
maxIndex = right;
}
// 如果根节点最大,天然就是一个堆,直接 break
if (maxIndex == index)
break;
// 否则根节点和大节点做交换,并继续堆化
swap(arr, index, maxIndex);
index = maxIndex;
}
}
public int[] sort() {
// 先构建堆结构
int[] maxHeap = buildHeap();
// 循环,把堆顶(最大的)换到最后面,再重新堆化
int count = nums.length;
while (count > 0) {
swap(maxHeap, 1, count);
count--;
heapify(maxHeap, 1, count);
}
return maxHeap;
}
}