交换排序（冒泡排序，快速排序），插入排序（直接插入排序，希尔排序），选择排序（简单选择排序，堆排序），归并排序，基数排序
冒泡排序(Bubble Sort)
冒泡排序步骤：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public class BubbleSort {
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
|
快速排序(Quick Sort)
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。
快速排序步骤
- 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot）
- 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
- 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序
递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| public class QuickSort {
public static void quickSort(int[] arr, int start, int end) {
if (start < end) {
int pivot = arr[start];
int low = start;
int high = end;
while (low < high) {
while (low < high && pivot <= arr[high]) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= pivot) {
low++;
}
arr[high] = arr[low];
}
arr[low] = pivot;
quickSort(arr, start, low);
quickSort(arr, low + 1, end);
}
}
}
|
插入排序(Insert Sort)
插入排序原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。举个例子来说：插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌面上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。
插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大且其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或逆序数组进行排序要快得多。
插入排序步骤：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public class InsertSort {
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
}
|
希尔排序(Shell Sort)
希尔排序是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public class ShellSort {
public static void shellSort(int[] arr) {
for (int d = arr.length / 2; d > 0; d /= 2) {
for (int i = d; i < arr.length; i++) {
int temp = arr[i];
int j = i - d;
while (j >= 0 && arr[j] > temp) {
arr[j + d] = arr[j];
j -= d;
}
arr[j + d] = temp;
}
}
}
}
|
选择排序(Selection Sort)
选择排序是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
它有两个很鲜明的特点：
运行时间与输入无关。为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息。这种性质在某些情况下是缺点，因为使用选择排序的人可能会惊讶的发现，一个已经有序的数组或是主键全部相等的数组和一个元素随机排列的数组所用的排序时间竟然一样长！相比之下，其它算法会更善于利用输入的初始状态。
数据移动是最少的。每次交换都会改变两个数组元素的值，因此选择排序用了\(N\)次交换——交换次数和数组大小是线性关系。其它的任何算法都不具备这个特征（大部分的增长数量级都是线性对数或平方级别）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public class SelectionSort {
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
if (i != minIndex) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
}
|
堆排序(Heap Sort)
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
通常堆是通过一维数组来实现的。在数组起始位置为0的情形中：
- 父节点i的左子节点在位置\((2i+1)\)
- 父节点i的右子节点在位置\((2i+2)\)
- 子节点i的父节点在位置\(((i-1)/2)\)
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余\(n-1\)个元素重新构造成一个堆，这样会得到\(n\)个元素的次小值。如此反复执行，便能得到一个有序序列了
堆排序的步骤
- 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。
- 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| public class HeapSort {
public static void heapsort(int[] arr) {
int start = (arr.length - 1) / 2;
for (int i = start; i >= 0; i--) {
maxHeap(arr, arr.length, i);
}
for (int i = arr.length - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
maxHeap(arr, i, 0);
}
}
public static void maxHeap(int[] arr, int size, int index) {
int leftNode = 2 * index + 1;
int rightNode = 2 * index + 2;
int max = index;
if (leftNode < size && arr[leftNode] > arr[max]) {
max = leftNode;
}
if (rightNode < size && arr[rightNode] > arr[max]) {
max = rightNode;
}
if (max != index) {
int temp = arr[index];
arr[index] = arr[max];
arr[max] = temp;
maxHeap(arr, size, max);
}
}
}
|
归并排序(Merge Sort)
归并排序是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。
归并排序的基本思路是将数组分成二组\(A，B\)，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。要让\(A，B\)两组内部数据有序，可以再将\(A，B\)组各自分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数组，再合并数组就完成了归并排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| public class MergeSort {
public static void mergesort(int[] arr, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
mergesort(arr, low, mid);
mergesort(arr, mid + 1, high);
}
int[] temp = new int[high - low + 1];
int i = low;
int j = mid + 1;
int index = 0;
while (i <= mid && j <= high) {
if (arr[i] <= arr[j]) {
temp[index] = arr[i];
i++;
} else {
temp[index] = arr[j];
j++;
}
index++;
}
while (j <= high) {
temp[index] = arr[j];
j++;
index++;
}
while (i <= mid) {
temp[index] = arr[i];
i++;
index++;
}
for (int k = 0; k < temp.length; k++) {
arr[k + low] = temp[k];
}
}
}
|
基数排序(Radix Sort)
基数排序是一种非比较型整数排序算法，其原理是将所有待比较数值（正整数）统一为同样的数字长度，数字较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| public class RadixSort {
public static void radixsort(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int maxlength = (max + "").length();
int[][] temp = new int[10][arr.length];
int[] counts = new int[10];
for (int i = 0, n = 1; i < maxlength; i++, n *= 10) {
for (int j = 0; j < arr.length; j++) {
int ys = arr[j] / n % 10;
temp[ys][counts[ys]] = arr[j];
counts[ys]++;
}
int index = 0;
for (int k = 0; k < counts.length; k++) {
if (counts[k] != 0) {
for (int l = 0; l < counts[k]; l++) {
arr[index] = temp[k][l];
index++;
}
counts[k] = 0;
}
}
}
}
}
|