十大经典排序算法

动画和参考文章来源

冒泡排序_BubbleSort

冒泡排序是通过多次的比较和交换逐渐将序列排序的方法。大(小)的元素会经过交换浮出水面。

  • 每次对相邻的两个数进行比较,若符合大小关系,则交换两个数;
  • 每经过一次排序,将最大(小)的数放在后(前)面,剩下的未排序.length - 1。

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package 十大经典排序算法;
//冒泡排序
public class _1_BubbleSort {
public static int[] bubbleSort(int[] array) {
if (array.length == 0)
return array;
for (int i = 0; i < array.length; i++)
for (int j = 0; j < array.length - 1 - i; j++)
if (array[j + 1] < array[j]) {
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
return array;
}

public static void main(String[] args) {
int[] arr = {9, 8, 3, 6};
bubbleSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}

选择排序_SelectionSort

选择排序,每次遍历序列,找到最小(大)的数,并放在序列的最前面,对剩下未排序的序列重复上述操作。

  • 每次初始设定为未序列的元素第一个为最小(大)元素,首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置;

  • 再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾;

  • 重复第二步,直到所有元素均排序完毕。

img

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
package 十大经典排序算法;
//选择排序
public class _2_SelectionSort {
public static int[] selectionSort(int[] array) {
if (array.length == 0)
return array;

for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i; j < array.length; j++) {
if (array[j] < array[minIndex]) //找到最小的数
minIndex = j; //将最小数的索引保存
}
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
return array;
}

public static void main(String[] args) {
int[] arr = {8, 9, 1, 4, 2, 3, 6, 7, 5};
selectionSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}

插入排序_InsertionSort

插入排序的基本操作就是从未排序的序列中取出一个数,插入到已经排序序列的正确位置中。

img

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
package 十大经典排序算法;

public class _3_InsertionSort {
public static int[] insertSort(int[] arr) {
if(arr == null || arr.length < 2)
return arr;
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int k = i - 1;
while(k >= 0 && arr[k] > temp)
k--;
//腾出位置插进去,要插的位置是 k + 1;
for(int j = i ; j > k + 1; j--)
arr[j] = arr[j-1];
//插进去
arr[k+1] = temp;
}
return arr;
}

public static void main(String[] args) {
int[] arr = {8, 9, 1, 4, 2, 3, 6, 7, 5};
insertSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}

希尔排序_ShellSort

img

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
package 十大经典排序算法;
//希尔排序
public class _4_ShellSort {
public static void shellSort(int[] arr) {
//不断的缩小增量 interval:间隔
for (int interval = arr.length / 2; interval > 0; interval = interval / 2) {
for (int i = interval; i < arr.length; i++) {
int target = arr[i];
int j = i - interval;
while ((j > -1) && (target < arr[j])) {
arr[j + interval] = arr[j];
j -= interval;
}
arr[j + interval] = target;
}
}
}

public static void main(String[] args) {
int[] arr = {8, 9, 1, 4, 2, 3, 6, 7, 5};
shellSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}

归并排序_MergeSort

img

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
package 十大经典排序算法;
// 归并排序
public class _5_MergeSort {
public static int[] mergeSort(int[] arr, int left, int right) {
// 如果 left == right,表示数组只有一个元素,则不用递归排序
if (left < right) {
// 把大的数组分隔成两个数组
int mid = (left + right) / 2;
// 对左半部分进行排序
arr = mergeSort(arr, left, mid);
// 对右半部分进行排序
arr = mergeSort(arr, mid + 1, right);
//进行合并
merge(arr, left, mid, right);
}
return arr;
}

// 合并函数,把两个有序的数组合并起来
// arr[left..mif]表示一个数组,arr[mid+1 .. right]表示一个数组
private static void merge(int[] arr, int left, int mid, int right) {
//先用一个临时数组把他们合并汇总起来
int[] a = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
a[k++] = arr[i++];
} else {
a[k++] = arr[j++];
}
}
while(i <= mid) a[k++] = arr[i++];
while(j <= right) a[k++] = arr[j++];
// 把临时数组复制到原数组
for (i = 0; i < k; i++) {
arr[left++] = a[i];
}
}

public static void main(String[] args) {
int[] arr = {8, 9, 1, 4, 2, 3, 6, 7, 5};
mergeSort(arr, 0 , arr.length - 1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}

快速排序_QuickSort

img

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
package 十大经典排序算法;

public class _6_QuickSort {
public static int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
//获取中轴元素所处的位置
int mid = partition(arr, left, right);
//进行分割
arr = quickSort(arr, left, mid - 1);
arr = quickSort(arr, mid + 1, right);
}
return arr;
}

private static int partition(int[] arr, int left, int right) {
//选取中轴元素
int pivot = arr[left];
int i = left + 1;
int j = right;
while (true) {
// 向右找到第一个小于等于 pivot 的元素位置
while (i <= j && arr[i] <= pivot) i++;
// 向左找到第一个大于等于 pivot 的元素位置
while(i <= j && arr[j] >= pivot ) j--;
if(i >= j)
break;
//交换两个元素的位置,使得左边的元素不大于pivot,右边的不小于pivot
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
arr[left] = arr[j];
// 使中轴元素处于有序的位置
arr[j] = pivot;
return j;
}
public static void main(String[] args) {
int[] arr = {8, 9, 1, 4, 2, 3, 6, 7, 5};
quickSort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}

堆排序_HeapSort

img

img

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
package 十大经典排序算法;
// 堆排序
public class _7_HeapSort {
public static int[] heapSort(int[] arr) {
int n = arr.length;
//构建大顶堆
for (int i = (n - 2) / 2; i >= 0; i--) {
downAdjust(arr, i, n - 1);
}
//进行堆排序
for (int i = n - 1; i >= 1; i--) {
// 把堆顶元素与最后一个元素交换
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
// 把打乱的堆进行调整,恢复堆的特性
downAdjust(arr, 0, i - 1);
}
return arr;
}

//下沉操作
public static void downAdjust(int[] arr, int parent, int n) {
//临时保存要下沉的元素
int temp = arr[parent];
//定位左孩子节点的位置
int child = 2 * parent + 1;
//开始下沉
while (child <= n) {
// 如果右孩子节点比左孩子大,则定位到右孩子
if(child + 1 <= n && arr[child] < arr[child + 1])
child++;
// 如果孩子节点小于或等于父节点,则下沉结束
if (arr[child] <= temp ) break;
// 父节点进行下沉
arr[parent] = arr[child];
parent = child;
child = 2 * parent + 1;
}
arr[parent] = temp;
}
public static void main(String[] args) {
int[] arr = {8, 9, 1, 4, 2, 3, 6, 7, 5};
heapSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}

计数排序_CountingSort

img

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
package 十大经典排序算法;
//计数排序
public class _8_CountingSort {
public static int[] countingSort(int[] arr) {
if(arr == null || arr.length < 2) return arr;

int n = arr.length;
int max = arr[0];
// 寻找数组的最大值
for (int i = 1; i < n; i++) {
if(max < arr[i])
max = arr[i];
}
//创建大小为max的临时数组
int[] temp = new int[max + 1];
//统计元素i出现的次数
for (int i = 0; i < n; i++) {
temp[arr[i]]++;
}
int k = 0;
//把临时数组统计好的数据汇总到原数组
for (int i = 0; i <= max; i++) {
for (int j = temp[i]; j > 0; j--) {
arr[k++] = i;
}
}
return arr;
}
public static void main(String[] args) {
int[] arr = {8, 9, 1, 4, 2, 3, 6, 7, 5};
countingSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}

桶排序_BucketSort

img

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
50
51
52
53
54
55
56
package 十大经典排序算法;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;

//桶排序
public class _9_BucketSort {
public static int[] bucketSort(int[] arr) {
if(arr == null || arr.length < 2) return arr;

int n = arr.length;
int max = arr[0];
int min = arr[0];
// 寻找数组的最大值与最小值
for (int i = 1; i < n; i++) {
if(min > arr[i])
min = arr[i];
if(max < arr[i])
max = arr[i];
}
//和优化版本的计数排序一样,弄一个大小为 min 的偏移值
int d = max - min;
//创建 d / 5 + 1 个桶,第 i 桶存放 5*i ~ 5*i+5-1范围的数
int bucketNum = d / 5 + 1;
ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>(bucketNum);
//初始化桶
for (int i = 0; i < bucketNum; i++) {
bucketList.add(new LinkedList<Integer>());
}
//遍历原数组,将每个元素放入桶中
for (int i = 0; i < n; i++) {
bucketList.get((arr[i]-min)/d).add(arr[i] - min);
}
//对桶内的元素进行排序,我这里采用系统自带的排序工具
for (int i = 0; i < bucketNum; i++) {
Collections.sort(bucketList.get(i));
}
//把每个桶排序好的数据进行合并汇总放回原数组
int k = 0;
for (int i = 0; i < bucketNum; i++) {
for (Integer t : bucketList.get(i)) {
arr[k++] = t + min;
}
}
return arr;
}

public static void main(String[] args) {
int[] arr = {8, 9, 1, 4, 2, 3, 6, 7, 5};
bucketSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}

基数排序_RadixSort

img

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
50
51
52
53
54
55
56
package 十大经典排序算法;

import java.util.ArrayList;
import java.util.LinkedList;

//基数排序
public class _10_RadixSort {
public static int[] radixSort(int[] arr) {
if(arr == null || arr.length < 2) return arr;

int n = arr.length;
int max = arr[0];
// 找出最大值
for (int i = 1; i < n; i++) {
if(max < arr[i]) max = arr[i];
}
// 计算最大值是几位数
int num = 1;
while (max / 10 > 0) {
num++;
max = max / 10;
}
// 创建10个桶
ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>(10);
//初始化桶
for (int i = 0; i < 10; i++) {
bucketList.add(new LinkedList<Integer>());
}
// 进行每一趟的排序,从个位数开始排
for (int i = 1; i <= num; i++) {
for (int j = 0; j < n; j++) {
// 获取每个数最后第 i 位是数组
int radio = (arr[j] / (int)Math.pow(10,i-1)) % 10;
//放进对应的桶里
bucketList.get(radio).add(arr[j]);
}
//合并放回原数组
int k = 0;
for (int j = 0; j < 10; j++) {
for (Integer t : bucketList.get(j)) {
arr[k++] = t;
}
//取出来合并了之后把桶清光数据
bucketList.get(j).clear();
}
}
return arr;
}
public static void main(String[] args) {
int[] arr = {8, 9, 1, 4, 2, 3, 6, 7, 5};
radixSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}