10种排序算法

排序算法是最基本最入门的东西了,回顾排序算法的时候好像回到了大一。。

排序算法

冒泡遍历

两两交换。两层遍历。

选择排序

我感觉最接近人类思维的排序了,我最早就是用这个写的排序。就是找个最小的放到前面,然后剩下的里面再找个最小的。两层遍历。

插入排序

两层遍历。分成无序的一堆,有序的一堆,每次无序里面拿一个放到有序里面合适的位置就好了。

希尔排序

感觉出场率很低。用一个增量 d 排序,每次 x 和 x + d 比较。然后 d 再除以 2 ,直到 d 变成 0 结束。我看网上一般增量取的都是 5 。

归并排序

分治。两个排好序的数组合成成一个数组。时间复杂度 O(nlogn) ,而且还稳定。可惜需要 O(n) 额外的空间。

快速排序

简单来说就是选一个元素,比这个小的放到左边,比这个大的放到右边,然后再对左边和右边递归。平均时间复杂度 O(nlogn) 。最差的时候就是每次选到本来就是最小的,或者最大的,就会退化成 O(n^2) 。

随便找了个算法题,写了个快排。 hdu1040 。

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
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] numbers = new int[1005];
while(n-- > 0)
{
int num = scanner.nextInt();

for(int i = 0; i < num; i++)
{
numbers[i] = scanner.nextInt();
}

QuickSort(numbers, 0, num - 1);

for(int i = 0; i < num; i++) {
if (i == 0) {
System.out.print(numbers[i]);
} else {
System.out.printf(" %d", numbers[i]);
}
}
System.out.println();
}
}

static void swap(int[] numbers, int left, int right)
{
int temp = numbers[left];
numbers[left] = numbers[right];
numbers[right] = temp;
}

static void QuickSort(int[] numbers, int left, int right)
{
if(left >= right) return;
int nextLeft = left, nextRight = right;
while(left < right)
{
while(left < right && numbers[right] >= numbers[left]) right--;
swap(numbers, left, right);
while(left < right && numbers[left] <= numbers[right]) left++;
swap(numbers, left, right);
}
QuickSort(numbers, nextLeft, left - 1);
QuickSort(numbers, left + 1, nextRight);
}
}

堆排序

一个完全二叉树。因为完全二叉树直接用数组就可以模拟。根结点放在 1 下标,方便计算。

最后一个元素下标就是 n 。初始化的时候,调整 1 ~ n / 2 的结点。取出元素的时候,拿出根结点,然后把 n 下标的元素放到 根结点,然后调整根结点,维护这个堆。

同样也用 hdu1040 写了个堆排序。

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
57
58
59
60
61
62
63
64
65
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] heap = new int[1005];
while(n-- > 0)
{
int num = scanner.nextInt();

for(int i = 1; i <= num; i++)
{
heap[i] = scanner.nextInt();
}

HeapSort(heap, num);

for(int i = 1; i <= num; i++) {
if (i == 1) {
System.out.print(heap[i]);
} else {
System.out.printf(" %d", heap[i]);
}
}
System.out.println();
}
}

static void swap(int[] heap, int n, int m)
{
int temp = heap[n];
heap[n] = heap[m];
heap[m] = temp;
}

static void adjustHeap(int[] heap, int now, int n)
{
while(2 * now <= n)
{
int next = (2 * now + 1 > n || heap[2 * now] > heap[2 * now + 1])
? 2 * now : 2 * now + 1;
if(heap[next] > heap[now])
swap(heap, now, next);
else
break;
now = next;
}
}

static void HeapSort(int[] heap, int n)
{
for(int i = n / 2; i >= 1; i--)
{
adjustHeap(heap, i, n);
}

for(int i = n; i >= 1; i--)
{
swap(heap, 1, i);
adjustHeap(heap, 1, i - 1);
}
}
}

计数排序

要求输入的数范围确定,然后用一个数组来模拟计数每个元素的个数。

桶排序

计数排序的升级版。比如 1 来放 0 - 9 的数,放到里面后对每个非空桶再排序,减少了一些空间的浪费。

基数排序

得到最大数的位数。先对个位排序,然后十位数排序,直到超过最大位。