【练习】不同排序算法执行时间比较

插入：

    template<typename DataType>
    void insert(DataType D[], int length) {
        DataType key;
        for (int j = 2; j < length; j++) {
             key = D[j];//先保存D[j]的位置，因为它可能会被替换
            int i = j - 1;
            while (i > 0 && D[i] > key) {
                D[i + 1] = D[i];//如果在j前面的元素比该元素大，将该元素后移动一个位置
                i--;//i继续前移进行扫描，直到它刚好大于它前面的元素 小于它后面的元素
            }
            D[i+1] = key;//插入刚刚的key值 注意是i+1
        }
}
    //们将D[0]作为哨兵元素，存储待排序元素

冒泡：

#include<stdio.h>
#include<time.h>
void swap(int& a, int& b) {
    int t;
    t = a;
    a = b;
    b = t;
}
void bubble(int a[], int n) {
    int i = n - 1;//i是下一趟需要参与排序交换的元素的最大下标
    while (i > 0) {
        int minindext = 0;//设置一开始的标志是0
        for (int j = 0; j < i; j++) {
            if (a[j + 1] < a[j]) {
                swap(a[j + 1], a[j]);
            }
            minindext = j;//此时为交换之后更小的元素的索引
        }
        i = minindext;

    }
}
int main()
{
    int a[1000] = { 0 };
    for (int i = 0; i < 1000; i++)
    {
        a[i] = rand() % 1000 + 1;
    }
    bubble(a, 1000);
    for (int i = 0; i < 1000; i++)
    {
        cout<<a[i]<<",";
    }
    printf("Time used = %.2f\n", (double)clock() / CLOCKS_PER_SEC);
}

注意：如果不写swap函数，而是直接在bubble函数中交换两个数字，发现它们最后并没有发生交换。

快速排序:

template<class T> int partition(T data[], int p, int r) {
    int i = p - 1; int j = p;
    for (j = p; j < r; j++) {
        if (data[j] <= data[r]) {
            i++;
           
            swap(data[i], data[j]);
        }
    }
    swap(data[i+1], data[r]);
    return i + 1;
}
template <class T>
void quickSort(T data[], int p, int r) {
    int position = 0;
    if (p < r) {
        position = partition(data, p, r);
        quickSort(data, p, position - 1);
        quickSort(data, position+1, r);
    }
}

int main()
{
    int a[1000] = { 0 };
    for (int i = 0; i < 1000; i++)
    {
        a[i] = rand() % 1000 + 1;
    }
    quickSort(a, 0,999);
    for (int i = 0; i < 1000; i++)
    {
        cout<<a[i]<<",";
    }
    printf("Time used = %.2f\n", (double)clock() / CLOCKS_PER_SEC);
}

易错点:swap(data[i+1], data[r]);
return i + 1;注意是i+1 ,如果写成i无法排序
我们设置变量p 和r 表示数组的首尾元素下标，选取数组最右边的元素为我们第一次排序的划界元素，记为S[r]。那么我们就需要将S[p]，S[p+1]，…，S[r–1]组成的序列进行子序列划分
我们设置变量i=p–1，即最前面元素的前一个，设置变量j = p。反复执行如下步骤：
（1）执行j+1，如果S[j]≤S[r]，交换S[i+1]与S[j]的值，i=i+1，j=j+1；如果S[j]≥S[r]，i 不变，j=j+1；
（2）到j=r–1 时，停止步骤（1）。
重复执行上述步骤直至停止后，交换S[i+1]与S[r]的值，划界元素放在了其最终位置上，其左边的元素均小于等于它，右边的元素均大于它。

归并排序：

void merge(int aa[], int b [], int c[],int lenA, int lenB) {
    int count = 0;
    int i = 0, j = 0;
    while (count < lenA + lenB) {
        if (aa[i] < b[j]) {
            c[count] = aa[i];
            count++;
            i++;

        }
        else {
            c[count] = b[j];
            count++;
            j++;
        }
        if (i == lenA) {
            while (j < lenB) {
                c[count] = b[j];
                count++;
                j++;
            }
        }
        else if(j == lenB){
            while (i < lenA) {
                c[count] = aa[i];
                count++;
                i++;
            }
        }
    }
}

void mergesort(int a[], int n) {
    if (n > 1) //记得要加判断条件n>1
    {
        int* b = new int[n / 2];
        int* c = new int[n - n / 2];
        for (int i = 0; i < n / 2; i++) {
            b[i] = a[i];
        }
        int k = n / 2;
        for (int j = 0; j < n - n / 2; j++) {
            c[j] = a[j + k];
        }
        
        mergesort(b, n / 2);
        mergesort(c, n - n / 2);
        merge(b, c, a, n / 2, n - n / 2);
    }
}
int main()
{
    int a[1000] = { 0 };
    for (int i = 0; i < 1000; i++)
    {
        a[i] = rand() % 1000 + 1;
    }
    mergesort(a, 1000);
    for (int i = 0; i < 1000; i++)
    {
        cout << a[i] << ",";
    }
    printf("Time used = %.2f\n", (double)clock() / CLOCKS_PER_SEC);
}

归并排序是排序两个已经排序好了的数组，原数组要先拆成两个子数组，
注意：一定不能遗漏对于i和j达到a或者b末尾的判断，否则会出现乱码。当i到达a的末尾，则遍历b剩下的数组直接赋给c

跟之前的对比归并排序时间是最长的。