排序算法_交换排序

#排序算法_交换排序
前天刚学了排序算法中的交换排序，分别为冒泡排序，快速排序，现在我们来实它。

冒泡排序

冒泡排序的实现就是在数组中对相邻的两个元素进行交换，每次循环都将最大的一个元素沉到最底，从而实现排序。

void bubblesort(int a[], int n)
{
    int bound, i, exchange, t;
    exchange = n;
    while (exchange)
    {
        bound = exchange;
        exchange = 0;
        for (i = 1; i < bound; i++)
        {
            if (a[i] > a[i + 1])
            {
                t = a[i];
                a[i] = a[i + 1];
                a[i + 1] = t;
                exchange = i;
            }
        }
    }
}

最好情况O（0）
最坏情况O（$n^2$）
平均复杂度（$n^2$）

快速排序

快速排序，原理是选取数组中一个处于相对于中间的值，然后其他的数值和其交换。当元素基本有序时，时间复杂度最高。

int partition(int a[], int first, int end)
{
    int i, j;
    i = first;
    j = end;
    int t, e;
    while (i < j && r[i] <= r[j]) j--;
        if (i < j)
        {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
            i++;
        }
        while (i < j && r[i] <= r[j]) i++;
        if (i < j)
        {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
            j--
        }
        return j;
 }
    void quicksort(int a[], int first, int end)
    {
        int pivotpos;
        while(first<end){
        pivotpos = partition(a, first, end);
        quicksort(r, first, pivotpos - 1);
        quicksort(r, pivotpos + 1, end);
        }
    }

时间复杂度为O（n$log_2$n）