数据结构中的常用算法总结

发表于 | 分类于

数据结构中的常用算法总结

首先介绍4个可视化数据结构的网址,推荐度从前往后

  1. visualgo
  2. sorting
  3. Data Structure Visualizations
  4. algo-visualizer

书籍

  1. Algorithms, 4th Edition
  2. topal

排序 sort

  1. insert
  2. 折半
  3. shell
  4. bubble
  5. quick
  6. select
  7. heap
  8. merge
  9. 基数

Insertion Sort

ALGORITHM

1
2
3
4
5
for i = 1:n-1,
    for (j = i; 1 <= j and a[j-1] > a[j]; j--)
        swap a[j-1, j]
    → invariant: a[1..i] is sorted
end

注解: 默认数组a下标就是1开始. k从i开始,例如一开始就是从第2个元素起步a[2]和第一个元素a[1]比较, 一趟比较完后k随着i++进行下一趟比较, i是用来确定一趟的最后一个元素位置. k>1是说最后比较只会是a[1] a[2] 不会a[0] a[1]因为不存在a[0], 下标从1开始, 最后一趟是从a[n-1] a[n]开始比较.

注意这个不需要一个数组 用来特别往后移动.

外层循环记录着每趟起始和终止位置,代表趟数;内层是比较方式. 要根据可视化的过程来决定外层怎么写. 比如select的 是小的放最前还是大的放最外层不一样.

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
/* 
插入排序 
基本思想：将元素逐个添加到已经排好序的数组中去。 
平均时间复杂度O(n^2) 
最好时间复杂度O(n) 
最坏时间复杂度O(n^2) 
空间复杂度O(1) 
*/  
void insert_sort (int a[], int n)
{
      
    for(int i = 1; i <= n-1; i++){//假设第0个已在正确位置，从第一个开始插入
        //第i趟插入需要在[0，i-1]中从后往前找到i的合适位置
        for ( int j = i; 1 <= j && a[j-1] > a[j]; j--){
            swap(a[j-1],a[j]);
        }
    }
}

void insert_sort (int a[], int n) {
    //要进行n-1趟插入
    for (int i = 1; i <= n-1; i++) {
        for (int j = i; 0 < j && a[j-1] > a[j]; j--) {  // 0<=j 不对哦 j是从1开始
            swap(a[j-1], a[j]);
        }
    }
}

void insert_sort (int a[]) {
    int n = a.length;
    for (int i = 1; i <= n-1; i++) {
        for (int j = i; 1 <= j && a[j-1] < a[j]; j--) {
            swap(a[j-1], a[j]);
        }
    }
}

//在内循环中将较大的元素一次性向右移动而不是交换两个元素，这样访问数组的次数将减半 。其代码如下：
真的么?
void sort(int[] data) {
    int size = data.length;
    for (int i = 1; i < size; i++) {
        int temp = data[i];
        int index = 0; //要插入的位置
        for (int j = i; j >= 1; j--) {
            if (temp < data[j-1]) {
                data[j] = data[j-1];
            }else {
                index = j;
                break;
            }
        }
        data[index] = temp;
    }
}

DISCUSSION

尽管存在最坏情况(worst-case)是O(n2), 也就是逆序(reversed)的情况下, insertion sort 在data几乎有序(这个叫adaptive)和问题size很小(这个叫low overhead 低开销)的情况下还是一个很好的选择.

还有他是stable的, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead 分治divide-and-conquer sorting algorithms, such as merge sort or quick sort.

PROPERTIES

  • Stable
  • O(1) extra space
  • O(n2) comparisons and swaps
  • Adaptive: O(n) time when nearly sorted
  • Very low overhead

二分

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
将直接插入排序中寻找a[i]插入位置的方法改为二分查找，然后再一次性向右移动元素。

public void sort(int[] a) {
    int n = a.length;
    for (int i = 1; i <= n-1; i++) {
        int num = binaryFind(a, a[i], 0, i-1);
        int temp = a[i];
        //num后的元素向后移动
        for (int j = i; num < j; j--) {
           a[j] = a[j-1];
        }
        a[num] = temp;
    }
}

//找出元素应在数组中插入的位置
public int binaryFind(int[] data, int temp, int down, int up) {
    if(up<down || up>data.length || down<0) {
        System.out.println("下标错误");
    }
    if(temp < data[down]) return down;
    if(temp > data[up]) return up+1;
    int mid = (up-down)/2 + down;
    if(temp == data[mid]) {
        return mid + 1;
    }else if(temp < data[mid]) {
        up = mid-1;
    }else if(temp > data[mid]) {
        down = mid+1;
    }
    return binaryFind(data,temp, down, up);
}

Shell Sort

ALGORITHM

1
2
3
4
5
6
7
h = 1
while h < n, h = 3*h + 1
while h > 0,
    h = h / 3
    for k = 1:h, insertion sort a[k:h:n]
    → invariant: each h-sub-array is sorted
end

注解: 首先按n大小计算递增序列,这里是按1 4 13 40 来, 然后从最大的h开始. 注意有一步h = h / 3 这就是比n小的最大的h, 因为前一个while跳出就是h>n的情况,还得返回去. 然后a[1,4] a[2, 5] 这样按insertion sort比较 a[k:h:n] 是从k到n以k为间隔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* 
5、希尔排序 
基本思想：将无序数组分成若干个子序列，子序列不是逐段分割的，而是相隔特定增量。对各个子序列进行插入排序。 
然后再选择一个更小的增量，再将数组分割成多个子序列进行排序。最后选择增量为1，即使用直接插入排序，使最终数组成为有序数组。 
平均时间复杂度O(n^1.3) 
最好时间复杂度O(n) 
最坏时间复杂度O(n^2) 
空间复杂度O(1) 
*/  
void shell_sort(int a[], int n)
{
    int gap;
    for( gap = n/2; gap > 0; gap /= 2){
        for(int i = gap; i < n; i ++){
            for(int j = i - gap; j >= 0 && a[j] < a[j + gap]; j-=gap){//每个元素与自己组内的元素进行插入排序
                swap(a[j], a[j + gap]);
            }
        }
    }
}
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
void shell_sort(int a[], int n)  
{  
    int h = 1;
    while (h < n) {
        h = 3*h +1;
    }
    while (h>0) {
        h = h/3;
        for ( int k = 0; k <= h-1; k++) { //根据增量分成若干组  每个h对应趟数
            // insert_sort的理解
            for(int i = k+h; i <= n-1; i=i+h){//假设第0个已在正确位置，从第一个开始插入  
                for ( int j = i; k+h <= j && a[j-h] > a[j]; j=j-h){  //不能加 k<= j 用k+h <= j也对
                    swap(a[j-h],a[j]);
                }
            }
        }
        //for ( int k = 0; k <= h-1; k++) { //根据增量分成若干组  
            // insert_sort()
            // for(int i = k+h; i <= n-1; i=i+h){//假设第0个已在正确位置，从第一个开始插入  
            //     for ( int j = i; k <= j && a[j-h] > a[j]; j=j-h){
            //         swap(a[j-h],a[j]);
            //     }
            // }
        //}
    }
} 


//核心算法，增量序列 1 4 13 ....（3*h+1）
void sort(int[] a) {
    int n = a.length;
    int h = 1;
    while(h < n/3) // 注意这里变了 
        h = 3*h + 1;
    while(h > 0 ) {
        for(int i = h; i <= n-1; i++) { //这种事按4的比完,再按5比完.而不是048这样. 8的这种后面会比到的
            for(int j = i; h <= j && a[j-h] > a[j]; j = j-h) {
                swap(a[j-h], a[j]);
            }
        }
        h = h/3;
    }

}

DISCUSSION

shell sort最坏情况时间复杂度(The worse-case time complexity)依赖于递增序列(the increment sequence). 这里所使用的the increments 1 4 13 40 121…, 时间复杂度是 O(n3/2). For other increments, time complexity is known to be O(n4/3) and even O(n·lg2(n)). 既不存在时间复杂度的紧上界，也不知道最佳增量序列。

Because shell sort is based on insertion sort, shell sort inherits insertion sort’s adaptive properties. The adapation is not as dramatic because shell sort requires one pass through the data for each increment, but it is significant. For the increment sequence shown above, there are log3(n) increments, so the time complexity for nearly sorted data is O(n·log3(n)).

Because of its low overhead, relatively simple implementation, adaptive properties, and sub-quadratic time complexity, shell sort may be a viable alternative to the O(n·lg(n)) sorting algorithms for some applications when the data to be sorted is not very large.

PROPERTIES

  • Not stable
  • O(1) extra space
  • O(n3/2) time as shown (see below)
  • Adaptive: O(n·lg(n)) time when nearly sorted

Bubble Sort

ALGORITHM

1
2
3
4
5
6
7
8
9
for i = n-1:0,
    swapped = false
    for j = 1:i; n--
        if a[j-1] > a[j],
            swap a[j-1,j]
            swapped = true
    → invariant: a[i..n-1] in final position
    break if not swapped
end

注意 Bubble 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
/* 
冒泡排序 
基本思想： 不断比较相邻的两个数，让较大的数不断地往后移。经过一番比较，就选出了最大的数。经过第二轮比较，就选出了次大的数。以此类推。 
那么对于大小为N的数组，需要N-1轮比较。 
平均时间复杂度O（N^2） 
最好情况O（N） 
最坏情况O（N^2） 
空间复杂度O（1） 
*/  
void bubble_sort(int a[],int n)
{
    //要进行N-1轮比较, 这里记录趟数
    for(int i = 0; i <= n-2; i++ )//[0,n-2]恰好n-1轮比较
    {
        bool is_sorted = true;  // 是否交换的
        for(int j = 1; j <= n-1-i; j++)//已经排好序的最后i个不用比较，要比较的数的个数为n-i个，那么需要比较的次数为n-i-1
        {
            if(a[j-1] > a[j]){
                is_sorted = false;
                swap(a[j-1],a[j]);
            }
        }
        if(is_sorted)//如果没有发生交换，说明已经排好序了，提前退出循环,所以最好情况下时间复杂度为O（N）
            break;
    }
}

void bubble_sort(int a[],int n)
{
    for(int i = n-1; 1 <= i; i-- ) // 这个好理解
    {
        bool is_sorted = true;  // 是否交换的标志
        for(int j = 1; j <= i; j++)
        {
            if(a[j-1] > a[j]){
                is_sorted = false;
                swap(a[j-1],a[j]);
            }
        }
        if(is_sorted) break;
    }
}

DISCUSSION

Bubble sort has many of the same properties as insertion sort, but has slightly higher overhead. In the case of nearly sorted data, bubble sort takes O(n) time, but requires at least 2 passes through the data (whereas insertion sort requires something more like 1 pass).

PROPERTIES

  • Stable
  • O(1) extra space
  • O(n2) comparisons and swaps
  • Adaptive: O(n) when nearly sorted

Quick Sort

ALGORITHM

1
2
3
4
5
6
7
8
9
10
11
12
_# choose pivot_
swap a[1,rand(1,n)]

_# 2-way partition_
k = 1
for i = 2:n, if a[i] < a[1], swap a[++k,i]
swap a[1,k]
_→ invariant: a[1..k-1] < a[k] <= a[k+1..n]_

_# recursive sorts_
sort a[1..k-1]
sort a[k+1,n]

注意 Quick 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/* 
3、快速排序 
基本思想：采用分而治之的思想，将要排序的数分成左右两部分，其中一部分的数据比key小，另一部分数据比key大。然后将所分得的两部分数据进行同样的划分。重复执行以上的划分操作。
平均时间复杂度O（Nlog2(N)）
最好情况O（Nlog2(N)）
最坏情况O（N^2）
空间复杂度O（Nlog2(N)）
*/ 
int partition(int arr[], int low, int high)//返回划分的中间值
{
    int key;
    key = arr[low];//相当于在索引low处挖坑，下一个就要找合适的据来填坑
    if (low > high) return;

    while(low < high)
    {
        while(low < high && key <= arr[high]){
            high --;
        }
        if(low < high)
            arr[low ++] = arr[high];//找到合适的数据填到了lo坑，但是形成了high坑，继续找合适的数据
        while( low < high && arr[low] <= key)
            low ++;
        if( low < high)
            arr[high --] =  arr[low];//low又成了坑

    arr[low] = key;//将key填到这个坑
    return low;
    }
}
void quick_sort(int num[], int low, int high)
{
    int pos;
    if(low < high){
        pos = partition(num, low, high);
        quick_sort(num, low, pos-1);
        quick_sort(num, pos+1, high);
    }
}

/*快速排序非递归版*/  
void quicksort2(int num[], int low, int high)
{
    int key = num[low];
    stack<int> s;
    if(low < high){
        int pos = partition(num, low, high);
        if(pos-1 > low){
            s.push(pos - 1);
            s.push(low);
        }
        if(pos+1 < high){
            s.push(high);
            s.push(pos + 1);
        }
        while(!s.empty()){
            int l = s.top();
            s.pop();
            int r = s.top();
            s.pop();
            pos = partition(num, l, r);
            if(pos - 1 > l){
                s.push(pos - 1);
                s.push(l);
            }
            if(pos + 1 < r){
                s.push(r);
                s.push(pos + 1);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void quick_sort(int arr[],int low,int high)
{
    int i=low,j=high,key=arr[low];//i j 是需要的 low high用来递归 不能动

    if(i > j)
        return ;

    while(i < j)
    {
        while(i < j && key <= arr[j]){
            j --;
        }
        if(i < j)
            arr[i ++] = arr[j];//找到合适的数据填到了low坑，但是形成了high坑，继续找合适的数据
        while( i < j && arr[i] <= key)
            i ++;
        if( i < j)
            arr[j --] =  arr[i];//low又成了坑
    }
	arr[i] = key;//将key填到这个坑 一趟后

    quick_sort(arr,low,i-1);
    quick_sort(arr,i+1,high);
}

DISCUSSION

When carefully implemented, quick sort is robust and has low overhead. When a stable sort is not needed, quick sort is an excellent general-purpose sort – although the 3-way partitioning version should always be used instead.

The 2-way partitioning code shown above is written for clarity rather than optimal performance; it exhibits poor locality, and, critically, exhibits O(n2) time when there are few unique keys. A more efficient and robust 2-way partitioning method is given in Quicksort is Optimal by Robert Sedgewick and Jon Bentley. The robust partitioning produces balanced recursion when there are many values equal to the pivot, yielding probabilistic guarantees of O(n·lg(n)) time and O(lg(n)) space for all inputs.

With both sub-sorts performed recursively, quick sort requires O(n) extra space for the recursion stack in the worst case when recursion is not balanced. This is exceedingly unlikely to occur, but it can be avoided by sorting the smaller sub-array recursively first; the second sub-array sort is a tail recursive call, which may be done with iteration instead. With this optimization, the algorithm uses O(lg(n)) extra space in the worst case.

PROPERTIES

  • Not stable
  • O(lg(n)) extra space (see discussion)
  • O(n2) time, but typically O(n·lg(n)) time
  • Not adaptive

Quick Sort 3 Way

ALGORITHM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
_# choose pivot_
swap a[n,rand(1,n)]

_# 3-way partition_
i = 1, k = 1, p = n
while i < p,
  if a[i] < a[n], swap a[i++,k++]
  else if a[i] == a[n], swap a[i,--p]
  else i++
end
_→ invariant: a[p..n] all equal_
_→ invariant: a[1..k-1] < a[p..n] < a[k..p-1]_

_# move pivots to center_
m = min(p-k,n-p+1)
swap a[k..k+m-1,n-m+1..n]

_# recursive sorts_
sort a[1..k-1]
sort a[n-p+k+1,n]

DISCUSSION

The 3-way partition variation of quick sort has slightly higher overhead compared to the standard 2-way partition version. Both have the same best, typical, and worst case time bounds, but this version is highly adaptive in the very common case of sorting with few unique keys.

The 3-way partitioning code shown above is written for clarity rather than optimal performance; it exhibits poor locality, and performs more swaps than necessary. A more efficient but more elaborate 3-way partitioning method is given in Quicksort is Optimal by Robert Sedgewick and Jon Bentley.

When stability is not required, quick sort is the general purpose sorting algorithm of choice. Recently, a novel dual-pivot variant of 3-way partitioning has been discovered that beats the single-pivot 3-way partitioning method both in theory and in practice.

PROPERTIES

  • Not stable
  • O(lg(n)) extra space
  • O(n2) time, but typically O(n·lg(n)) time
  • Adaptive: O(n) time when O(1) unique keys

Selection Sort

ALGORITHM

1
2
3
4
5
6
7
8
for i = 0:n-1,
    min = i
    for j = i+1:n-1, 
        if a[min] > a[j], min = j
    → invariant: a[min] smallest of a[i..n-1]
    swap a[i,min]
    → invariant: a[0..i] in final position
end

注意 每一趟可以选择最小的放到最前面,也可以选最大的放最后面. k使用存放临时极小值(极大值). 最后一趟比完才最后确定.

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
/* 
选择排序 
基本思想：首先，选出最小的数放在第一位，然后选择第二小的数，放在第二位；以此类推，直到所有的数从小到大排列. 
那么，对于大小为N的数组需要N-1轮选择过程。第i轮选取第i小的数，请将其放在第i个位置上。
不稳定 
平均时间复杂度O（N^2）
最好情况O（N^2）
最坏情况O（N^2）
空间复杂度O（1）
*/ 
  
void select_sort(int a[], int n)  
{
    for(int i = 0; i <= n-1-1; i++){//进行n-1轮选择,也就是i的取值为[0，n-2] 
        int min_index = i;
        //记录第i小的数所在的索引
        for(int j = i + 1; j <= n-1; j++){
            if(a[min_index] > a[j]) //有点谐
                min_index = j;
        }
        if(i != min_index){//根据记录的第i小的数的索引，找到了第i小的数。然后将该数放到其正确位置。也就是第i个位置。
            swap(a[i] , a[min_index]);
        }
    }
}

void select_sort(int[] a) {
    int n = a.length;
    for(int i = 0; i <= n-1; i++) {
        int min = i;
        for(int j = i+1; j <= n-1; j++) {
            if(a[j] < a[min])
                min=j;
        }
        swap(a[i], a[min]);
    }
}

DISCUSSION

从比较结果来看, 最好不要用selection sort should never be used. It does not adapt to the data in any way (notice that the four animations above run in lock step), 运行时间一直是平方项(quadratic).

但是有一个优点 selection sort 可以减少交换项数目. 可以应用于交换项cost很大的的情况.

PROPERTIES

  • Not stable
  • O(1) extra space
  • Θ(n2) comparisons
  • Θ(n) swaps
  • Not adaptive

Heap Sort

ALGORITHM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# heapify
for i = n/2:1, sink(a,i,n)
→ invariant: a[1,n] in heap order

# sortdown
for i = 1:n,
    swap a[1,n-i+1]
    sink(a,1,n-i)
    → invariant: a[n-i+1,n] in final position
end

# sink from i in a[1..n]
function sink(a,i,n):
    # {lc,rc,mc} = {left,right,max} child index
    lc = 2*i
    if lc > n, return # no children
    rc = lc + 1
    mc = (rc > n) ? lc : (a[lc] > a[rc]) ? lc : rc
    if a[i] >= a[mc], return # heap ordered
    swap a[i,mc]
    sink(a,mc,n)

注意完全二叉, 用的是数组,首先是建堆,然后再排序.
建堆(heapify)中确定大顶堆还是小顶堆. 从最后一个非叶子节点(n/2)开始比较,往上比较.

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
//堆排序:树形选择排序，将带排序记录看成完整的二叉树，第一步：建立初堆，第二步：调整堆
//第二步：调整堆
void HeapAdjust(int a[],int s,int n)  //但习惯上用大顶堆
{
    //调整为小根堆，从小到大
    int rc=a[s];
    for(int j=2*s;j<=n;j*=2)
    {
        if(j<n && a[j]>a[j+1])//判断左右子数大小,找小的
            j++;
        if(rc<=a[j])
            break;
        a[s]=a[j]; //小的放上去
        s=j;
    }
    a[s]=rc;    //大的放下来
}
//第一步：建初堆
void CreatHeap(int a[],int n)
{
    //小根堆,从最后一个非叶子节点开始,根是1
    for(int i=n/2;i>0;i--)
        HeapAdjust(a,i,n);
}
//整合
void HeapSort(int a[],int n)
{
    CreatHeap(a,n);//第一步，建立初堆
    for(int i=n;i>1;i--)
    {
        int x=a[1];//堆顶与最后一个元素互换
        a[1]=a[i];
        a[i]=x;
        HeapAdjust(a,1,i-1);
    }
}
int main()
{
    int n;
    cin>>n;
    int *a=new int[n+1];
    for(int j=1;j<n;j++)//注意：这里是从1开始的
        cin>>a[j];
    HeapSort(a,n);
    for(int i=1;i<n;i++)
        cout<<a[i];
    delete []a;
}
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
#include<stdio.h>

//　　创建大堆顶，i为当节点，n为堆的大小
//    从第一个非叶子结点i从下至上，从右至左调整结构
//    从两个儿子节点中选出较大的来与父亲节点进行比较
//    如果儿子节点比父亲节点大，则进行交换
void CreatHeap(int a[], int i, int  n) {

    //    注意数组是从0开始计数，所以左节点为2*i+1，右节点为2*i+2
    // 这里改了吧 应该从1开始好
    for (; i >= 0; --i)
    {
        int left = i * 2 + 1;    //左子树节点
        int right = i * 2 + 2;    //右子树节点
        int j = 0;
        //选出左右子节点中最大的
        if (right < n) {
            a[left] > a[right] ? j= left : j = right;
        }
        else
            j = left;
        //交换子节点与父节点
        if (a[j] > a[i]) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
}

//    进行堆排序，依次选出最大值放到最后面
void HeapSort(int a[]) {
    int n = a.length-1;
    //初始化构造堆
    CreatHeap(a, n/2-1, n);
　　//交换第一个元素和最后一个元素后，堆的大小减1
    for (int j = n-1; j >= 0; j--) {
        
        //最后一个元素和第一个元素进行交换
        int tmp = a[0];
        a[0] = a[j];
        a[j] = tmp;

        int i = j / 2 - 1;  //有必要-1么
        CreatHeap(a, i, j);
    }
}
int main() {
    int a[] = { 10,6,5,7,12,8,1,3,11,4,2,9,16,13,15,14 };
    int n = sizeof(a) / sizeof(int);
    HeapSort(a);
    printf("排序好的数组为：");
    for (int l = 0; l < n; l++) {
        printf("%d ", a[l]);
    }
    printf("\n");
    return 0;
}
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
void HeapAdjust(int a[],int s,int n)  //但习惯上用大顶堆
{
    //调整为大根堆，
    int rc = a[s];
    for(int j = 2*s; j <= n; j*=2) // 有左子树,
    {
		if (j+1 <= n ) {	//如果右子树存在
			if(a[j] < a[j+1])//判断左右子数大小
				j++;			
		} else if(rc >= a[j]) {  //根和左子树比
			break;
		}    
        a[s] = a[j]; //大的放上去
        s = j;		// 继续往大的子树的子树找,保证当前堆是大顶堆
    }
    a[s] = rc;    //小的放下来
}
//第一步：建初堆
void CreatHeap(int a[],int n)
{
    //小根堆,从最后一个非叶子节点开始,根是1
    for(int i = n/2; i > 0; i--)
        HeapAdjust(a,i,n);
}
//整合
void HeapSort(int a[],int n)
{
    CreatHeap(a,n);//第一步，建立初堆
    for(int i = n-1 ; i >= 2; i--)  //这里从n-1到2就可以了
    {
		swap(a[1], a[i]);
        HeapAdjust(a,1,i-1);
    }
}

DISCUSSION

Heap sort is simple to implement, performs an O(n·lg(n)) in-place sort, but is not stable.

The first loop, the Θ(n) “heapify” phase, puts the array into heap order. The second loop, the O(n·lg(n)) “sortdown” phase, repeatedly extracts the maximum and restores heap order.

The sink function is written recursively for clarity. Thus, as shown, the code requires Θ(lg(n)) space for the recursive call stack. However, the tail recursion in sink() is easily converted to iteration, which yields the O(1) space bound.

Both phases are slightly adaptive, though not in any particularly useful manner. In the nearly sorted case, the heapify phase destroys the original order. In the reversed case, the heapify phase is as fast as possible since the array starts in heap order, but then the sortdown phase is typical. In the few unique keys case, there is some speedup but not as much as in shell sort or 3-way quicksort.

PROPERTIES

  • Not stable
  • O(1) extra space (see discussion)
  • O(n·lg(n)) time
  • Not really adaptive

Merge Sort

ALGORITHM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# split in half
m = n / 2

# recursive sorts
sort a[1..m]
sort a[m+1..n]

# merge sorted sub-arrays using temp array
b = copy of a[1..m]
i = 1, j = m+1, k = 1
while i <= m and j <= n,
    a[k++] = (a[j] < b[i]) ? a[j++] : b[i++]
    → invariant: a[1..k] in final position
while i <= m,
    a[k++] = b[i++]
    → invariant: a[1..k] in final position
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
/* 
6、归并排序： 
基本思想：将待排序序列【0，n-1】看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表。再次归并，得到n/4个长度为4的有序表。 
依次类推，最后得到长度为n的1个有序表。 
所以归并排序其实要做两件事： 
1、先递归的分解数列， 
2、再合并数列就完成了归并排序。 
 
先来考虑如何合并？ 
每次合并过程中都要对两个有序的序列段进行合并，然后排序 
待合并的两个有序序列段分别为 R[low, mid] 和 R[mid+1, high] 
先将它们合并到一个暂存数组R2，合并完再将R2复制回R1中。 
这样一次合并排序就完成了。 
 
最好、最坏和平均时间复杂度都是O(nlogn)， 
空间复杂度是O(n) 
*/  
void merge(int a[], int low ,int mid, int high)  
{  
    int tmp[];
    int i,j,k;  
    i = low;  //i 和 j是临时会动的 所以新定义一个变量
    j = mid + 1;
    k = 0;//k是存放临时合并数组的下表
  
    while( i <= mid && j <= high){
        if( a[i] < a[j])  // 小的元素放tmp
            tmp[k++] = a[i++];
        else 
            tmp[k++] = a[j++];
    }
    while( i <= mid)
        tmp[k++] = a[i++];
    while( j <= high)
        tmp[k++] = a[i++];
    //最后再复制回a
    for(i = 0; i < k; i++ )
        a[low+i] = tmp[i];//!!!!此处a是从low开始，tmp是从0开始。
}

//以上完整程序

void mergeSort (int a[]) {
    sort (a, 0, a.length-1);
}

void sort (int a[], int left, int right) {
    if (left >= right) return ;
    int mid = (left+right) / 2;  // (right - left)/2 + left
    sort (a, left, mid);
    sort (a, mid+1, right);
    merge (a, left, mid, right);
    print(a);
}


//改进 还有换一种自底向上的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
首先考虑下如何将2个有序数列合并。这个非常简单，只要从比较2个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

//将有序数组a[]和b[]合并到c[]中
void MemeryArray(int a[], int n, int b[], int m, int c[])
{
 int i, j, k;

 i = j = k = 0;
 while (i < n && j < m)
 {
     if (a[i] < b[j])
         c[k++] = a[i++];
     else
         c[k++] = b[j++]; 
 }

 while (i < n)
     c[k++] = a[i++];

 while (j < m)
     c[k++] = b[j++];
}

DISCUSSION

Merge sort is very predictable. It makes between 0.5lg(n) and lg(n) comparisons per element, and between lg(n) and 1.5lg(n) swaps per element. The minima are achieved for already sorted data; the maxima are achieved, on average, for random data. If using Θ(n) extra space is of no concern, then merge sort is an excellent choice: It is simple to implement, and it is the only stable O(n·lg(n)) sorting algorithm. Note that when sorting linked lists, merge sort requires only Θ(lg(n)) extra space (for recursion).

Merge sort is the algorithm of choice for a variety of situations: when stability is required, when sorting linked lists, and when random access is much more expensive than sequential access (for example, external sorting on tape).

There do exist linear time in-place merge algorithms for the last step of the algorithm, but they are both expensive and complex. The complexity is justified for applications such as external sorting when Θ(n) extra space is not available.

PROPERTIES

  • Stable
  • Θ(n) extra space for arrays (as shown)
  • Θ(lg(n)) extra space for linked lists
  • Θ(n·lg(n)) time
  • Not adaptive
  • Does not require random access to data

基数排序

树中

堆说过了