Blog Of Leung

personal blog & work notes

View project onGitHub
　

几个排序算法实例

两个月没有更新博客了，今天重温一下几个常用的排序算法。

快速排序

快速排序是使用率极高的排序方法，属于分治法的一种，基本思想是先定一个基准数，通过一轮比较，把比基准数小的放在一边，比基准数大的放在另一边，从而形成了两个数列，然后分别对两边的数，递归进行上述过程，直至排序结束。

#include <stdio.h>

void QuickSort(int s[], int low, int high);
void Swap(int *a, int *b);

int main(void)
{
    int i, size;
    int s[] = {1, 5, 7, 3, 2, 9, 0, 8, 4, 6};
    size = sizeof(s) / sizeof(s[0]);
    QuickSort(s, 0, 9);
    for(i = 0; i < size; i++)
        printf("%d ", s[i]);
    printf("\n");

}

void QuickSort(int s[], int low, int high)
{
    int i, last;
    if(low < high) {
        last = low;
        for(i = low + 1; i <= high; i++) {
            if(s[i] < s[low])
                Swap(&s[i], &s[++last]);
        }
        Swap(&s[last], &s[low]);
        QuickSort(s, low, last - 1);
        QuickSort(s, last + 1, high);
    }

}

void Swap(int *a, int *b)
{
    if(a != b) {
        *a ^= *b;
        *b ^= *a;
        *a ^= *b;
    }
}

冒泡排序与选择排序

冒泡排序是逻辑最简单的排序之一，通过两层循环，相邻的数两两比较，把较大的放在后面，最多n-1轮之后，排序完成。 比较有意思的是，对比选择排序，可以发现两者的代码非常相似，选择排序是两层循环，但不是相邻的数进行比较，而是每一轮都寻找最小的一个数放在前面，然后在剩下的数中继续寻找最小的数排在第二位，直至排序完成。

#include <stdio.h>

void BubbleSort(int s[], int size);
void SelectSort(int s[], int size);
void Swap(int *a, int *b);

int main(void)
{
    int i, size;
    int s[] = {1, 6, 8, 9, 0, 8, 5, 4, 3, 2};
    size = sizeof(s) / sizeof(s[0]);
    //BubbleSort(s, size);
    SelectSort(s, size);
    for(i = 0; i < size; i++)
        printf("%d ", s[i]);
    printf("\n");

}

void BubbleSort(int s[], int size)
{
    int i, j;
    for(i = 0; i < size -1; i++) {
        for(j = 0; j < size - 1 - i; j++) {
            if(s[j] > s[j + 1])
                Swap(&s[j], &s[j + 1]);
        }
    }

}

void SelectSort(int s[], int size)
{
    int i, j;
    for(i = 0; i < size; i++) {
        for(j = i + 1; j < size; j++) {
            if(s[j] < s[i])
                Swap(&s[j], &s[i]);
        }
    }
}

void Swap(int *a, int *b)
{
    if(a != b) {
        *a ^= *b;
        *b ^= *a;
        *a ^= *b;
    }
}

直接插入排序

直接插入排序,每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。 第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

#include <stdio.h>

void InsertSort(int s[], int size);

int main(void)
{
    int i, size;
    int s[] = {1, 4, 6, 8, 9, 0, 2, 3, 5, 7};
    size = sizeof(s) / sizeof(s[0]);
    InsertSort(s, size);
    for(i = 0; i < size; i++)
        printf("%d ", s[i]);
    printf("\n");

}

void InsertSort(int s[], int size)
{
    int i, j, k, temp;
    for(j = 1; j < size; j++) {
        i = 0;
        while(s[i] < s[j] && i < j)
            i++;
        if(i != j) {
            temp = s[j];
            for(k = j; k > i; k--)
                s[k] = s[k - 1];
            s[i] = temp;
        }
    }
}

堆排序

堆排序，这里讨论的是最大堆，父结点比左右孩子都要大，堆顶一定是所有元素中的最大值，因此可以快速地得到元素中的最大值。另外，堆的存储我们用数组来表示，父节点为i，左孩子就是2i+1，右孩子为2i+2。进行堆排序一般有三个过程：

堆调整：比较父节点和左右孩子，如果左右孩子比根节点的值大，则进行交换，以满足堆的定义

建立堆：数据一开始可以看作是无序的完全二叉树，建立堆就是对所有的非叶子节点进行堆调整

堆排序：首先建立堆，然后交换根节点与最后一个叶子节点，交换之后把最后的叶子节点当作是有序数组，然后循环上述过程，重新对剩下的数进行堆调整，并依次把最大数交换到叶子节点中。最后，形成有序数组。

#include <stdio.h>

void Swap(int *a, int *b);
void HeapSort(int s[], int size);
void BuildHeap(int s[], int size);
void HeapAdjust(int s[], int i, int size);

int main(void)
{
    int i, size;
    int s[] = {1, 4, 6, 8, 0, 9, 2, 3, 5, 7};
    size = sizeof(s) / sizeof(s[0]);
    HeapSort(s, size);
    for(i = 0; i < size; i++)
        printf("%d ", s[i]);
    printf("\n");
}

void HeapAdjust(int s[], int i, int size)
{
    int lchild = 2 * i + 1;
    int rchild = 2 * i + 2;
    int max = i;
    if(i <= size / 2) {
        if(lchild <= size && s[lchild] > s[max])
            max = lchild;
        if(rchild <= size && s[rchild] > s[max])
            max = rchild;
        if(max != i) {
            Swap(&s[max], &s[i]);
            HeapAdjust(s, max, size);
        }
    }
}

void BuildHeap(int s[], int size)
{
    int i;
    for(i = size / 2; i >= 0; i--)
        HeapAdjust(s, i, size);
}

void HeapSort(int s[], int size)
{
    int i;
    BuildHeap(s, size);
    for(i = size - 1; i >= 0; i--) {
        Swap(&s[i], &s[0]);
        HeapAdjust(s, 0, i - 1);
    }
}

void Swap(int *a, int *b)
{
    if(a != b) {
        *a ^= *b;
        *b ^= *a;
        *a ^= *b;
    }
}

归并排序

归并排序的思想是，把两个有序数列合并成一个有序的数列，而产生有序数列的方法是不断地进行分隔，当每一个数列都只有一个数的时候，即可认为是有序的，然后循环地把这些有序数列合并起来。

#include <stdio.h>

void MergeSort(int s[], int low, int high, int temp[]);
void MergeArray(int s[], int low, int mid, int high, int temp[]);

int main(void)
{
    int i;
    int s[] = {1, 3, 5, 7, 9, 2, 4, 6, 8};
    size = sizeof(s) / sizeof(s[0]);
    int p[size];
    MergeSort(s, 0, size - 1, p);
    for(i = 0; i < size; i++)
        printf("%d ", s[i]);
    printf("\n");
}

void MergeSort(int s[], int low, int high, int temp[])
{
    if(low < high) {
       int mid = (low + high) / 2;
       MergeSort(s, low, mid, temp);
       MergeSort(s, mid + 1, high, temp);
       MergeArray(s, low, mid, high, temp);
    }

}

//合并有序数列
void MergeArray(int s[], int low, int mid, int high, int temp[])
{
    int k = 0;
    int i = low;
    int j = mid + 1;
    while(i <= mid && j <= high) {
        if(s[i] <= s[j]) {
            temp[k++] = s[i++];
        }
        else {
            temp[k++] = s[j++];
        }
    }
    while(i <= mid)
        temp[k++] = s[i++];
    while(j <= high)
        temp[k++] = s[j++];
    for(i = 0; i < k; i++)
        s[low + i] = temp[i];

}

Author:leung

25 Nov 2014

← Home

comments powered by Disqus