读书笔记: 算法 Algorithm(bubble Sort,select Sort, Insert Sort, Quick Sort, Merge Sort, Heap Sort)

1
2
3
4
// 排序n个不同元素的判定树的高度至少为(log2 (n!))+1
// 任何基于关键字比较的排序算法,在最坏情况下的时间复杂度为O(n(logn2 n))

#define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))

Bubble sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//冒泡排序O(n2),稳定
void bubblesort(int list[],int n){
    int i,j,temp,flag;
    for(i=0;i<n;i++){
        flag=0;
        for(j=n-1;j>i;j--){
            if(list[j-1]>list[j]){
                SWAP(list[j], list[j-1], temp);
                flag=1;
            }
        }
        if(flag == 0) break;  //没有交换则跳出。
    }

}

Select sort

1
2
3
4
5
6
7
8
9
10
11
//选择排序 O(n2),不稳定
void select_sort(int list[],int n){
    int temp,i,j,min;
    for(i=0;i<n-1;i++){
        min=i;
        for(j=i+1;j<n;j++){
            if(list[j] < list[min]) min=j;
        }
        SWAP(list[i],list[min],temp); //导致不稳定
    }
}

Insert sort

1
2
3
4
5
6
7
8
9
10
11
12
13
//插入排序 O(n2),稳定,适合规模小的序列表
//变形:折半插入排序,减少查找次数,移动次数不变
//     链表插入排序,不需移动记录,只能使用顺序查找
void insert_sort(int list[],int n){
    int i,j,next;
    for(i=1;i<n;i++){
        next = list[i];
        for(j=i-1;j>=0 && next < list[j];j--){
            list[j+1]=list[j];
        }
        list[j+1]=next;
    }
}

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
//快速排序O(n2),平均O(nlogn),不稳定
void quicksort(int list[],int left,int right){
    int i,j,pivot;
    int temp; //用于swap

    if(left<right){
        i=left;j=right+1;
        pivot=list[left];
        do{
            do
                i++;
            while(list[i]<pivot);
            do
                j--;
            while(list[j]>pivot);
            if(i<j)
                SWAP(list[i], list[j], temp);
        }while(i<j);
        SWAP(list[left], list[j], temp);
        quicksort(list, left, j-1);
        quicksort(list, j+1, right);
    }
}

Merge 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
//归并两个已排序的表,空间复杂性O(n)
void merge(int list[],int sorted[],int i,int m,int n){
    //merge two sorted files : list[i]..list[m] and list[m+1]..list[n] to a sorted list sorted[i]..sorted[n]
    int j,k,t;
    j=m+1;//index for the second sublist
    k=i;//index for the sorted list
    while(i<=m && j<=n){
        if(list[i] <= list[j])
            sorted[k++]=list[i++];
        else
            sorted[k++]=list[j++];
    }


        //sorted[k]..sorted[n] = list[j]..list[n]
        while(j<=n)
            sorted[k++]=list[j++];

        //sorted[k]..sorted[n] = list[i]..list[m]
        while(i<=m)
            sorted[k++]=list[i++];
}

void merge_pass(int list[],int sorted[],int n,int length){
    //perform one pass of the merge sort.
    //It merges adjacent(邻近) pairs of subfiles from list int sorted
    //n is the number of list,length is the length of the subfile
    int i,j;
    for(i=0;i<=n-2*length;i+=2*length){
        merge(list, sorted, i, i+length-1, i+2*length-1);
    }
    //#如果一段是正好可归并的数量而另一段则少于正好可归并的数量#
    if(i+length < n){
        merge(list, sorted, i, i+length-1, n-1);
    } else {
        for(j=i;j<n;j++){//#如果只剩下一段或者更少的数量#
            sorted[j]=list[j];
        }
    }

}

//总归并次数log2 n,每遍归并时间O(n),所以O(nlogn)
//额外空间开销与待排文件的记录个数成比例
void iter_merge_sort(int list[],int n){
    int length = 1;
//    int extra[MAX_SIZE];
    int extra[n];

    while(length < n){
        merge_pass(list, extra, n, length);
        length *=2;
        merge_pass(extra, list, n, length);
        length *=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
49
50
51
52
void wiki_merge(int array[], int low, int mid, int high)
{
    int i, k;
    int begin1 = low;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = high;

    //申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
    int *temp = (int *) malloc((high-low+1) * sizeof(int));

    //比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
    for (k = 0; begin1 <= end1 && begin2 <= end2; ++k)
    {
        if(array[begin1]<=array[begin2])
        {
            temp[k] = array[begin1++];
        }
        else
        {
            temp[k] = array[begin2++];
        }
    }

    //若第一个序列有剩余,直接拷贝出来粘到合并序列尾
    if(begin1 <= end1)
    {
        memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));
    }
    //若第二个序列有剩余,直接拷贝出来粘到合并序列尾
    if(begin2 <= end2)
    {
        memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));
    }
    //将排序好的序列拷贝回数组中
    memcpy(array+low, temp, (high-low+1)*sizeof(int));
    free(temp);
}

void wiki_merge_sort(int array[], unsigned int first, unsigned int last)
{
    int mid = 0;
    if(first<last)
    {
        /*mid = (first+last)/2;*/ /*注意防止溢出*/
        /*mid = first/2 + last/2;*/
        mid = (first & last) + ((first ^ last) >> 1);
        wiki_merge_sort(array, first, mid);
        wiki_merge_sort(array, mid+1,last);
        wiki_merge(array,first,mid,last);
    }
}

Heap 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
//调整最大堆
//该函数的参数为一颗二叉树T,T的左右子树均满足堆的性质,只有根节点可能不满足
//该函数调整T,使得整个二叉树都满足堆的性质
void adjust(int list[],int root,int n){
    int child;
    int temp;
    temp = list[root];
    child = 2* root; // left child
    while(child <=n){
        if ((child < n) && (list[child] < list[child+1])){
            child++;
        }
        if(temp > list[child]){ // compare root and max child
            break;
        } else {
            list[child/2]=list[child]; // move to parent
            child*=2;
        }
    }
    list[child/2]=temp;
}

//第二个for循环中,调用adjust共n-1次,且树的最大深度为log(2)(n+1),所以O(nlogn),不稳定
//注意堆的下标从1开始,list[0]不排序
void heapsort(int list[],int n){
    int i;
    int temp;

    for(i=n/2;i>0;i--){
        adjust(list, i, n);
    }
    for(i=n-1;i>0;i--){
        SWAP(list[1], list[i+1], temp);
        adjust(list, 1, i);
    }
}

Test

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
int main (int argc, const char * argv[])
{
    int list[] = {5,2,4,1,3};
    bubblesort(list,5);

    int i;
    for(i=0;i<5;i++){
        printf("%d",list[i]);
    }
    printf("\n");

    int list1[]={1,3,5,7,2,4,6,8};
    iter_merge_sort(list1,8);
    for(i=0;i<8;i++)
        printf("%d ",list1[i]);

    printf("\n");
    int list2[]={-1,26,5,77,1,61,11,59,15,48,19};
    heapsort(list2,10);
    for(i=1;i<=10;i++)
        printf("%d ",list2[i]);


    return 0;
}