数据结构基础排序算法

从小到大排序

1、冒泡

每次从第一个元素开始与右边相邻元素两两比较，将较大元素右移。

需要移动n-1次。

void bubble(int a[], int n)
{
    int i;
    int tmp;
    int j;
    for(j=n-; j>; j--) // 需要n-1轮冒泡
    {
        for(i=; i<j; i++) // 每轮冒泡将最大的移动到右侧
        {
            if(a[i] > a[i+])
            {
                tmp = a[i];
                a[i] = a[i+];
                a[i+] = tmp;
            }
        }
    }
}
           

2、选择

每次选择0到i-1位置最大元素放到i位置。i从n-1到0变化。

void select(int a[], int n)
{
    int i;
    int j;
    int max, u;
    int tmp;
    for(i=n-; i>; i--) // 需要选择n-1次
    {
        max = a[];
        u = ;
        for(j=; j<=i; j++) // 每次选择一个最大的放到右侧
        {
            if(max < a[j])
            {
                u = j;
                max = a[j];
            }
        }
        tmp = a[i];
        a[i] = a[u];
        a[u] = tmp;
    }
}
           

3、插入

每次把i位置元素插入到0到i-1合适位置。i从1到n-1。

void inserts(int a[], int n)
{
    int i;
    int j;
    int tmp;
    for(i=; i<n; i++) // 需要插入n-1次
    {
        tmp = a[i];
        for(j=i-; j>=; j--) // 每次选择数插入到前面排好序的数组
        {
            if(tmp < a[j]) // 插入时找到合适位置，其它元素向后顺延
            {
                a[j+] = a[j];
                if(j == ) // 需要插在第一位时特殊判断
                    a[j] = tmp;
            }
            else
            {
                a[j+] = tmp;
                break;
            }
        }
    }
}
           

4、快速

选取第一个为基准。将基准调整在中间位置，左边全是比基准小的。右边全是比基准大的。然后对左右分别递归快排。

调整方法：i指向基准，j指向数组最后一个元素。首先从右向左找到第一个比基准小的数，放到i位置，i++。然后从左往右找第一个比基准大的元素，放到j位置，j–。重复该过程，直到i>=j。将基准放到i位置。

void quick(int a[], int l, int r)
{
    if(l >= r) // 至少有两个元素
        return;

    int base = a[l]; // 选取第一个为基准
    int i = l;
    int j = r;

    while(i < j) // 至少有两个元素才需要快排
    {
        while(i < j &&a[j] >= base) // 从右向左找第一个比base小的
            j--;
        if(i < j) // 如果找到了
        {
            a[i] = a[j];
            i++;
        }
        while(i < j && a[i] <= base) // 从左向右找第一个比base大的
            i++;
        if(i < j) // 如果找到了
        {
            a[j] = a[i];
            j--;
        }
    }
    a[i] = base;
    quick(a, l, i-);
    quick(a, i+, r);
}
           

5、归并

将数组切分成均等的两份(允许前面数组比后面数组多一个元素)，分别递归这两部分，然后将这两部分合并成一部分。

合并方法：

对两部分的每个元素两两比较，较小者优先放到合并后的数组中。两部分长度不一致时，较长数组剩下元素依次放入合并后数组即可。

void merges(int a[], int l, int r)
{
    if(l >= r)
        return; // 至少有两个元素

    int mid = (l + r) / ; // 拆分进行归并排序两个子数组
    merges(a, l, mid);
    merges(a, mid+, r);

    // 合并两个子数组为新数组,再将新数组复制回去
    int t[r-l+];
    int k = ;
    int i = l;
    int j = mid+;
    while(i <= mid && j <= r)
    {
        if(a[i] <= a[j])
        {
            t[k] = a[i];
            i++;
        }
        else
        {
            t[k] = a[j];
            j++;
        }
        k++;
    }
    while(i <= mid)
    {
        t[k] = a[i];
        i++;
        k++;
    }
    while(j <= r)
    {
        t[k] = a[j];
        j++;
        k++;
    }
    for(i=; i<k; i++)
    {
        a[i+l] = t[i];
    }
}
           

测试

#include <stdio.h>

void outputa(int a[], int l, int r)
{
    int i;
    for(i=l; i<r; i++)
    {
        printf("%d ", a[i]);
    }
    printf("%d\n", a[i]);
}

int main()
{
    int a1[] = {, , , , , , };
    bubble(a1);
    printf("bubble sort...\n");
    outputa(a1, , );
    int a2[] = {, , , , , , };
    select(a2);
    printf("select sort...\n");
    outputa(a2, , );
    int a3[] = {, , , , , , };
    inserts(a3);
    printf("insert sort...\n");
    outputa(a3, , );
    int a4[] = {, , , , , , };
    quick(a4, , );
    printf("quick sort...\n");
    outputa(a4, , );
    int a5[] = {, , , , , , };
    merges(a5,  ,);
    printf("merge sort...\n");
    outputa(a5, , );
    return ;
}