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

Love The Way You Lie 2022-11-07 04:17 104阅读 0赞

插入：

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]作为哨兵元素，存储待排序元素

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]

冒泡：

#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函数中交换两个数字，发现它们最后并没有发生交换。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 1]

快速排序:

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\]的值，划界元素放在了其最终位置上，其左边的元素均小于等于它，右边的元素均大于它。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 2]  
归并排序：

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  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 3]  
跟之前的对比归并排序时间是最长的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]: /images/20221023/68b188c0309642e2b517cabfc4e849f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 1]: /images/20221023/af913b1d8dff4533b1d30597c7e15e54.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 2]: /images/20221023/b0027c395dde4bffb4519d2bd3c15f94.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 3]: /images/20221023/462fe45da1f04415880165ad765e20ac.png