1. 冒泡排序
image
private static void bubbleSort(int[] a) {
if (a == null || a.length == 0) {
return;
}
int length = a.length;
for (int i = 0; i < length - 1; i++) {
for (int j = i; j < length - 1 - i; j++) {
if (a[j] > a[j + 1])
swap(a, j, j + 1);
}
}
}
2. 快排
①. 从数列中挑出一个元素，称为”基准”（pivot）。
②. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
③. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。
/**
* 快排
* @param arr
* @param low
* @param high
*/
public static void quickSort(int arr[], int low, int high) {
if (arr == null || arr.length <= 0) {
return;
}
if (low >= high) {
return;
}
int left = low;
int right = high;
int temp = arr[left]; //挖坑1：保存基准的值
while (left < right) {
while (left < right && arr[right] >= temp) {
right--;
}
arr[left] = arr[right]; //坑2：从后向前找到比基准小的元素，插入到基准位置坑1中
while (left < right && arr[left] <= temp) {
left++;
}
arr[right] = arr[left]; //坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中
}
arr[left] = temp; //基准值填补到坑3中，准备分治递归快排
System.out.println("Sorting: " + Arrays.toString(arr));
quickSort(arr, low, left - 1);
quickSort(arr, left + 1, high);
}
3. 简单选择排序
每次选取最大的一个数字，放在数组未排序的最后一个，直到排序结束。
/**
* 选择排序
*
*/
private static void selectSort2(int[] a) {
if (a == null || a.length == 0) {
return;
}
int n = a.length;
while (n > 1) {
int pos = findMaxIndex(a, n);
swap(a, pos, n - 1);
n--;
}
}
/**
* 获取数组中最大数字的index
*/
public static int findMaxIndex(int[] a, int n) {
int max = a[0];
int pos = 0;
for (int i = 1; i < n; i++) {
if (a[i] > max) {
max = a[i];
pos = i;
}
}
return pos;
}
4. 堆排序
堆排序是一种树形选择排序方法，特点是在排序过程中将L[1···n]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点的内在关系，在当前无序区中选择关键字最大（或最小）元素。
- 父节点 parent = (i-1)/2;
- 左子节点 c1 = 2i+1;
- 右子节点 c2 = 2i+2;
数字：87 45 78 32 17 65 53 09
①从上到下，从左到右建堆
int parent = (last_node - 1) / 2;
根据数组最后一位可以得出【09】的根节点为【32】
倒着进行heapify
② 从倒数第二层左节点开始，与左右子树进行比较交换
③ 从第二步max位置依次递归直到顶端为最大数
④ 将根节点【87】与最后一位【09】交换，移出最后一位【87】，最后对根节点进行重新heapfy，将【09】与【78】进行交换……直到排序完成
/**
* 堆排序
*
* @param a
*/
private static void heapSort(int[] a) {
if (a == null || a.length == 0) {
return;
}
int n = a.length;
buildHeap(a, n);
for (int i = n - 1; i >= 0; i--) {
swap(a, i, 0); // 交换根节点和最后一个节点
heapify(a, i, 0); // 重新heapify
}
}
/**
* 父节点 parent = (i-1)/2;
* 左子节点 c1 = 2i+1;
* 右子节点 c2 = 2i+2;
*/
private static void heapify(int[] tree, int n, int i) {
if (i >= n)
return;
int c1 = 2 * i + 1;
int c2 = 2 * i + 2;
/*
* 左中右三个节点找最大值
*/
int max = i;
if (c1 < n && tree[c1] > tree[max])
max = c1;
if (c2 < n && tree[c2] > tree[max])
max = c2;
if (max != i) {
// 将最大值与i进行交换
swap(tree, max, i);
heapify(tree, n, max);
}
}
private static void buildHeap(int[] tree, int n) {
int last_node = n - 1;
int parent = (last_node - 1) / 2;
for (int i = parent; i >= 0; i--) {
heapify(tree, n, i);
}
}
5. 直接插入排序
从第二个数字开始，依次把数字插入到合适的位置。
/**
* 插入排序
*/
private static void insertSort(int[] a) {
if (a == null || a.length == 0) {
return;
}
int length = a.length;
for (int i = 1; i < length; i++) {
insert(a, i);
}
}
/**
* 把第n个数插入到数组a合适的位置
*/
private static void insert(int[] a, int n) {
int key = a[n];
int i = n;
while (a[i - 1] > key) {
a[i] = a[i - 1];
i--;
if (i == 0)
break;
}
a[i] = key;
}
6. 希尔排序
将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次再将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。
/**
* 希尔排序
*/
public static void shellSort(int a[]) {
if (a == null || a.length == 0) {
return;
}
int n = a.length;
for (int gap = n / 2; gap >= 1; gap = gap / 2) {
for (int i = 0; i + gap < n; i++) {
for (int j = 0; j + gap < n; j += gap) {
if (a[j] > a[j + gap]) {
swap(a, j, j + gap);
}
}
}
}
}
7. 归并排序
/**
* 归并
* 2, 8, 9, 10, 4, 5, 6, 7
*
* @param a
*/
public static void mergeSort(int[] a, int l, int r) {
if (l == r)
return;
int mid = (l + r) / 2;
// 左归并，右归并
mergeSort(a, l, mid);
mergeSort(a, mid + 1, r);
merge(a, l, mid + 1, r);
}
/**
* 合并一个从l-mid,r-mid排好序的数组
* 2, 8, 9, 10, 4, 5, 6, 7
* l = 0,mid=4,r=7
*/
private static void merge(int[] a, int l, int mid, int r) {
int leftSize = mid - l;
int rightSize = r - mid + 1;
int left[] = new int[leftSize];
int right[] = new int[rightSize];
/*
* 1. 构建两个数组
* left [2,8,9,10]
* right[4,5,6,7]
*/
for (int i = l; i < mid; i++) {
left[i - l] = a[i];
}
for (int i = mid; i <= r; i++) {
right[i - mid] = a[i];
}
/**
* 2.合并成1个
* i指向左数组第一个
* j指向右数组第一个
* k 指向空数组最左边
*/
int i = 0;
int j = 0;
int k = l;
while (i < leftSize && j < rightSize) {
if (left[i] < right[j]) {
a[k] = left[i];
i++;
k++;
} else {
a[k] = right[j];
j++;
k++;
}
}
/**
* 如果上面循环完毕，i仍旧没到达顶部，则把剩下的数字抄一下
*/
while (i < leftSize) {
a[k] = left[i];
i++;
k++;
}
/**
* 如果上面循环完毕，j仍旧没到达顶部，则把剩下的数字抄一下
*/
while (j < rightSize) {
a[k] = right[j];
j++;
k++;
}
}
8. 基数排序
- ① 取得数组中的最大数，并取得位数；
- ② arr为原始数组，从最低位开始取每个位组成radix数组；
-
③ 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
