資料結構基礎排序算法

從小到大排序

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 ;
}