1.冒泡排序

1.两两注意是相邻的两个元素的意思
2.如果有n个元素需要比较n-1次，每一轮减少1次比较
3.既然叫冒泡排序，那就是从下往上两两比较，所以看上去就跟泡泡往上冒一样。

#include <stdio.h>
void BubbleSort(int k[], int n)
{
    int i, j, temp, count1=0, count2=0;
    for( i=0; i < n-1; i++ )
    {
        for( j=i+1; j < n; j++ )
        {
            count1++;
            if( k[i] > k[j] )
            {
                count2++;
                temp = k[j];
                k[j] = k[i];
                k[i] = temp;
            }
        }
    }
    printf("总共进行了%d次比较，进行了%d次移动！", count1, count2);
}
int main()
{
    int i, a[10] = {1, 0, 2, 3, 4, 5, 6, 7, 8, 9};
    BubbleSort(a, 10);
    printf("排序后的结果是：");
    for( i=0; i < 10; i++ )
    {
        printf("%d", a[i]);
    }
    printf("\n\n");
    return 0;
}

#include <stdio.h>
void BubbleSort(int k[], int n)
{
    int i, j, temp, count1=0, count2=0;
    for( i=0; i < n-1; i++ )
    {
        for( j=n-1; j > i; j-- )
        {
            count1++;
            if( k[j-1] > k[j] )
            {
                count2++;
                temp = k[j-1];
                k[j-1] = k[j];
                k[j] = temp;
            }
        }
    }
    printf("总共进行了%d次比较，进行了%d次移动！", count1, count2);
}
int main()
{
    int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    BubbleSort(a, 10);
    printf("排序后的结果是：");
    for( i=0; i < 10; i++ )
    {
        printf("%d", a[i]);
    }
    printf("\n\n");
    return 0;
}

#include <stdio.h>
void BubbleSort(int k[], int n)
{
    int i, j, temp, count1=0, count2=0, flag;
    flag = 1;
    for( i=0; i < n-1 && flag; i++ )
    {
        for( j=n-1; j > i; j-- )
        {
            count1++;
            flag = 0;
            if( k[j-1] > k[j] )
            {
                count2++;
                temp = k[j-1];
                k[j-1] = k[j];
                k[j] = temp;
                flag = 1;
            }
        }
    }
    printf("总共进行了%d次比较，进行了%d次移动！", count1, count2);
}
int main()
{
    int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    BubbleSort(a, 10);
    printf("排序后的结果是：");
    for( i=0; i < 10; i++ )
    {
        printf("%d", a[i]);
    }
    printf("\n\n");
    return 0;
}

2.选择排序

#include <stdio.h>
void SelectSort(int k[], int n)
{
    int i, j, min, temp, count1=0, count2=0;
    for( i=0; i < n-1; i++ )
    {
        min = i;
        for( j=i+1; j < n; j++ )
        {
            count1++;
            if( k[j] < k[min] )
            {
                min = j;
            }
        }
        if( min != i )
        {
            count2++;
            temp = k[min];
            k[min] = k[i];
            k[i] = temp;
        }
    }
    printf("总共进行了%d次比较，进行了%d次移动！", count1, count2);
}
int main()
{
    int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    SelectSort(a, 10);
    printf("排序后的结果是：");
    for( i=0; i < 10; i++ )
    {
        printf("%d", a[i]);
    }
    printf("\n\n");
    return 0;
}

3.直接排序

#include <stdio.h>
void InsertSort(int k[], int n)
{
    int i, j, temp;
    for( i=1; i < n; i++ )
    {
        if( k[i] < k[i-1] )
        {
            temp = k[i];
            for( j=i-1; k[j] > temp; j-- )
            {
                k[j+1] = k[j];
            }
            k[j+1] = temp;
        }
    }
}
int main()
{
    int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    InsertSort(a, 10);
    printf("排序后的结果是：");
    for( i=0; i < 10; i++ )
    {
        printf("%d", a[i]);
    }
    printf("\n\n");
    return 0;
}

4.希尔排序

#include <stdio.h>
void InsertSort(int k[], int n)
{
    int i, j, temp;
    int gap = n;
    do
    {
        gap = gap/3 + 1;
        for( i=gap; i < n; i++ )
        {
            if( k[i] < k[i-gap] )
            {
                temp = k[i];
                for( j=i-gap; k[j] > temp; j-=gap )
                {
                    k[j+gap] = k[j];
                }
                k[j+gap] = temp;
            }
        }
    }while(gap > 1);
}
int main()
{
    int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
    InsertSort(a, 10);
    printf("排序后的结果是：");
    for( i=0; i < 10; i++ )
    {
        printf("%d", a[i]);
    }
    printf("\n\n");
    return 0;
}

5.快速排序

#include <stdio.h>
void swap(int k[], int low, int high)
{
    int temp;
    temp = k[low];
    k[low] = k[high];
    k[high] = temp;
}
int Partition(int k[], int low, int high)
{
    int point;
    point = k[low];
    while( low < high )
    {
        while( low < high && k[high] >= point )
        {
            high--;
        }
        swap(k, low, high);
        while( low < high && k[low] <= point )
        {
            low++;
        }
        swap(k, low, high);
    }
    return low;
}
void QSort(int k[], int low, int high)
{
    int point;
    if( low < high )
    {
        point = Partition(k, low, high);
        QSort(k, low, point-1);
        QSort(k, point+1, high);
    }
}
void QuickSort(int k[], int n)
{
    QSort(k, 0, n-1);
}
int main()
{
    int i, a[10] = {4, 2, 5, 0, 3, 9, 1, 7, 6, 8};
    QuickSort(a, 10);
    printf("排序后的结果是：");
    for( i=0; i < 10; i++ )
    {
        printf("%d", a[i]);
    }
    printf("\n\n");
    return 0;
}