主頁 >  其他 > 演算法--排序基礎

演算法--排序基礎

2020-09-16 22:04:45 其他

基礎的排序演算法

c++基礎

生成隨即測驗用例

 int *generateRandomArray(int n, int rangeL, int rangeR) {

        assert(rangeL <= rangeR);

        int *arr = new int[n];

        srand(time(NULL));
        for (int i = 0; i < n; i++)
            arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
        return arr;
    }

生成近乎有序的測驗用例

int *generateNearlyOrderedArray(int n, int swapTimes){

        int *arr = new int[n];
        for(int i = 0 ; i < n ; i ++ )
            arr[i] = i;

        srand(time(NULL));
        for( int i = 0 ; i < swapTimes ; i ++ ){
            int posx = rand()%n;
            int posy = rand()%n;
            swap( arr[posx] , arr[posy] );
        }

        return arr;
    }

拷貝陣列并回傳新陣列

 int *copyIntArray(int a[], int n){

        int *arr = new int[n];
        //* 在VS中, copy函式被認為是不安全的,此時可用for回圈:)
        copy(a, a+n, arr);
        return arr;
    }

列印陣列內容

template<typename T>
    void printArray(T arr[], int n) {

        for (int i = 0; i < n; i++)
            cout << arr[i] << " ";
        cout << endl;

        return;
    }

判斷陣列是否有序

    template<typename T>
    bool isSorted(T arr[], int n) {

        for (int i = 0; i < n - 1; i++)
            if (arr[i] > arr[i + 1])
                return false;

        return true;
    }

判斷排序正確性與排序時間

 template<typename T>
    void testSort(const string &sortName, void (*sort)(T[], int), T arr[], int n) {

        clock_t startTime = clock();
        sort(arr, n);
        clock_t endTime = clock();

        assert(isSorted(arr, n));
        cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;

        return;
    }

選擇排序

template<typename T>
void selectionSort(T arr[], int n){

    for(int i = 0 ; i < n ; i ++){

        int minIndex = i;
        for( int j = i + 1 ; j < n ; j ++ )
            if( arr[j] < arr[minIndex] )
                minIndex = j;

        swap( arr[i] , arr[minIndex] );
    }
}

選擇排序測驗

int main() {

    // 測驗模板函式，傳入整型陣列
    int a[10] = {10,9,8,7,6,5,4,3,2,1};
    selectionSort( a , 10 );
    for( int i = 0 ; i < 10 ; i ++ )
        cout<<a[i]<<" ";
    cout<<endl;

    // 測驗模板函式，傳入浮點數陣列
    float b[4] = {4.4,3.3,2.2,1.1};
    selectionSort(b,4);
    for( int i = 0 ; i < 4 ; i ++ )
        cout<<b[i]<<" ";
    cout<<endl;

    // 測驗模板函式，傳入字串陣列
    string c[4] = {"D","C","B","A"};
    selectionSort(c,4);
    for( int i = 0 ; i < 4 ; i ++ )
        cout<<c[i]<<" ";
    cout<<endl;

    return 0;
}

對選擇排序進行他優化(在每一輪中, 可以同時找到當前未處理元素的最大值和最小值)

template<typename T>
void selectionSort(T arr[], int n){

    int left = 0, right = n - 1;
    while(left < right){
        int minIndex = left;
        int maxIndex = right;

        // 在每一輪查找時, 要保證arr[minIndex] <= arr[maxIndex]
        if(arr[minIndex] > arr[maxIndex])
            swap(arr[minIndex], arr[maxIndex]);

        for(int i = left + 1 ; i < right; i ++)
            if(arr[i] < arr[minIndex])
                minIndex = i;
            else if(arr[i] > arr[maxIndex])
                maxIndex = i;

        swap(arr[left], arr[minIndex]);
        swap(arr[right], arr[maxIndex]);

        left ++;
        right --;
    }

    return;
}

插入排序

基本的插入排序(寫法二看著更像是高手，嘻嘻嘻)

template<typename T>
void insertionSort(T arr[], int n){

    for( int i = 1 ; i < n ; i ++ ) {

        // 尋找元素arr[i]合適的插入位置
        // 寫法1
//        for( int j = i ; j > 0 ; j-- )
//            if( arr[j] < arr[j-1] )
//                swap( arr[j] , arr[j-1] );
//            else
//                break;

        // 寫法2
        for( int j = i ; j > 0 && arr[j] < arr[j-1] ; j -- )
            swap( arr[j] , arr[j-1] );

    }

    return;
}

改進插入排序(將交換改為賦值)

template<typename T>
void insertionSort(T arr[], int n){

    for( int i = 1 ; i < n ; i ++ ) {

        T e = arr[i];
        int j; // j保存元素e應該插入的位置
        for (j = i; j > 0 && arr[j-1] > e; j--)
            arr[j] = arr[j-1];
        arr[j] = e;
    }

    return;
}

冒泡排序

template<typename T>
void bubbleSort( T arr[] , int n){

    bool swapped;

    do{
        swapped = false;
        for( int i = 1 ; i < n ; i ++ )
            if( arr[i-1] > arr[i] ){
                swap( arr[i-1] , arr[i] );
                swapped = true;

            }

        // 優化, 每一趟Bubble Sort都將最大的元素放在了最后的位置
        // 所以下一次排序, 最后的元素可以不再考慮
        n --;

    }while(swapped);
}

冒泡排序的另一種優化

template<typename T>
void bubbleSort2( T arr[] , int n){

    int newn; // 使用newn進行優化

    do{
        newn = 0;
        for( int i = 1 ; i < n ; i ++ )
            if( arr[i-1] > arr[i] ){
                swap( arr[i-1] , arr[i] );

                // 記錄最后一次的交換位置,在此之后的元素在下一輪掃描中均不考慮
                newn = i;
            }
        n = newn;
    }while(newn > 0);
}

希爾排序

在插入排序的基礎上改變

template<typename T>
void shellSort(T arr[], int n){

    // 計算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
    int h = 1;
    while( h < n/3 )
        h = 3 * h + 1;

    while( h >= 1 ){

        // h-sort the array
        for( int i = h ; i < n ; i ++ ){

            // 對 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
            T e = arr[i];
            int j;
            for( j = i ; j >= h && e < arr[j-h] ; j -= h )
                arr[j] = arr[j-h];
            arr[j] = e;
        }

        h /= 3;
    }
}

比較SelectionSort, InsertionSort和BubbleSort和ShellSort四種排序演算法的性能效率, ShellSort是這四種排序演算法中性能最優的排序演算法,以下是對20000個亂數的測驗

Selection Sort : 0.517969 s
Insertion Sort : 0.267192 s
Bubble Sort : 1.9947 s
Shell Sort : 0.003899 s

歸并排序

// 將arr[l...mid]和arr[mid+1...r]兩部分進行歸并
template<typename  T>
void __merge(T arr[], int l, int mid, int r){

    //* VS不支持動態長度陣列, 即不能使用 T aux[r-l+1]的方式申請aux的空間
    //* 使用VS, 可以使用new的方式申請aux空間
    //* 使用new申請空間, 不要忘了在__merge函式的最后, delete掉申請的空間:)
    T aux[r-l+1];
    //T *aux = new T[r-l+1];

    for( int i = l ; i <= r; i ++ )
        aux[i-l] = arr[i];

    // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
    int i = l, j = mid+1;
    for( int k = l ; k <= r; k ++ ){

        if( i > mid ){  // 如果左半部分元素已經全部處理完畢
            arr[k] = aux[j-l]; j ++;
        }
        else if( j > r ){  // 如果右半部分元素已經全部處理完畢
            arr[k] = aux[i-l]; i ++;
        }
        else if( aux[i-l] < aux[j-l] ) {  // 左半部分所指元素 < 右半部分所指元素
            arr[k] = aux[i-l]; i ++;
        }
        else{  // 左半部分所指元素 >= 右半部分所指元素
            arr[k] = aux[j-l]; j ++;
        }
    }

    //delete[] aux;
}

// 遞回使用歸并排序,對arr[l...r]的范圍進行排序
template<typename T>
void __mergeSort(T arr[], int l, int r){

    if( l >= r )
        return;

    int mid = (l+r)/2;
    __mergeSort(arr, l, mid);
    __mergeSort(arr, mid+1, r);
    __merge(arr, l, mid, r);
}

template<typename T>
void mergeSort(T arr[], int n){

    __mergeSort( arr , 0 , n-1 );
}

比較InsertionSort和MergeSort兩種排序演算法的性能效率，整體而言, MergeSort的性能最優，Merge Sort是一個O(nlogn)復雜度的演算法，可以在1秒之內輕松處理100萬數量級的資料，注意：不要輕易嘗試使用SelectionSort, InsertionSort或者BubbleSort處理100萬級的資料，否則，你就見識了O(n^2)的演算法和O(nlogn)演算法的本質差異：）

對于近乎有序的陣列, 陣列越有序, InsertionSort的時間性能越趨近于O(n)，所以可以嘗試, 當swapTimes（生成幾乎有序陣列時的引數，決定有序程度）比較大時, MergeSort更快，但是當swapTimes小到一定程度, InsertionSort變得比MergeSort快

對上面的排序進行優化

// 使用優化的歸并排序演算法, 對arr[l...r]的范圍進行排序
template<typename T>
void __mergeSort2(T arr[], int l, int r){

    // 優化2: 對于小規模陣列, 使用插入排序
    if( r - l <= 15 ){
        insertionSort(arr, l, r);
        return;
    }

    int mid = (l+r)/2;
    __mergeSort2(arr, l, mid);
    __mergeSort2(arr, mid+1, r);

    // 優化1: 對于arr[mid] <= arr[mid+1]的情況,不進行merge
    // 對于近乎有序的陣列非常有效,但是對于一般情況,有一定的性能損失
    if( arr[mid] > arr[mid+1] )
        __merge(arr, l, mid, r);
}

template<typename T>
void mergeSort2(T arr[], int n){

    __mergeSort2( arr , 0 , n-1 );
}

歸并排序進一步種優化

// 將arr[l...mid]和arr[mid+1...r]兩部分進行歸并
// 其中aux為完成merge程序所需要的輔助空間
template<typename  T>
void __merge2(T arr[], T aux[], int l, int mid, int r){

    // 由于aux的大小和arr一樣, 所以我們也不需要處理aux索引的偏移量
    // 進一步節省了計算量:)
    for( int i = l ; i <= r; i ++ )
        aux[i] = arr[i];

    // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
    int i = l, j = mid+1;
    for( int k = l ; k <= r; k ++ ){

        if( i > mid ){  // 如果左半部分元素已經全部處理完畢
            arr[k] = aux[j]; j ++;
        }
        else if( j > r ){  // 如果右半部分元素已經全部處理完畢
            arr[k] = aux[i]; i ++;
        }
        else if( aux[i] < aux[j] ) {  // 左半部分所指元素 < 右半部分所指元素
            arr[k] = aux[i]; i ++;
        }
        else{  // 左半部分所指元素 >= 右半部分所指元素
            arr[k] = aux[j]; j ++;
        }
    }

}

// 使用優化的歸并排序演算法, 對arr[l...r]的范圍進行排序
// 其中aux為完成merge程序所需要的輔助空間
template<typename T>
void __mergeSort2(T arr[], T aux[], int l, int r){

    // 對于小規模陣列, 使用插入排序
    if( r - l <= 15 ){
        insertionSort(arr, l, r);
        return;
    }

    int mid = (l+r)/2;
    __mergeSort2(arr, aux, l, mid);
    __mergeSort2(arr, aux, mid+1, r);

    // 對于arr[mid] <= arr[mid+1]的情況,不進行merge
    // 對于近乎有序的陣列非常有效,但是對于一般情況,有一定的性能損失
    if( arr[mid] > arr[mid+1] )
        __merge2(arr, aux, l, mid, r);
}


template<typename T>
void mergeSort2(T arr[], int n){

    // 在 mergeSort2中, 我們一次性申請aux空間,
    // 并將這個輔助空間以引數形式傳遞給完成歸并排序的各個子函式
    T *aux = new T[n];

    __mergeSort2( arr , aux, 0 , n-1 );

    delete[] aux;   // 使用C++, new出來的空間不要忘記釋放掉:)
}

Merge Sort 2 只開辟了一次輔助空間, 之后將這個輔助空間以引數形式傳遞給完成歸并排序的其他子函式,Merge Sort 2的性能優于 Merge Sort

使用自底向上的歸并排序演算法

template <typename T>
void mergeSortBU(T arr[], int n){

    // Merge Sort Bottom Up 無優化版本
   for( int sz = 1; sz < n ; sz += sz )
        for( int i = 0 ; i < n - sz ; i += sz+sz )
         // 對 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 進行歸并
         __merge(arr, i, i+sz-1, min(i+sz+sz-1,n-1) );

}

進行優化

template <typename T>
void mergeSortBU(T arr[], int n){

    // Merge Sort Bottom Up 優化
    // 對于小陣列, 使用插入排序優化
    for( int i = 0 ; i < n ; i += 16 )
        insertionSort(arr,i,min(i+15,n-1));

    for( int sz = 16; sz < n ; sz += sz )
        for( int i = 0 ; i < n - sz ; i += sz+sz )
            // 對于arr[mid] <= arr[mid+1]的情況,不進行merge
            if( arr[i+sz-1] > arr[i+sz] )
                __merge(arr, i, i+sz-1, min(i+sz+sz-1,n-1) );

}

Merge Sort BU 也是一個O(nlogn)復雜度的演算法，雖然只使用兩重for回圈,所以，Merge Sort BU也可以在1秒之內輕松處理100萬數量級的資料,注意：不要輕易根據回圈層數來判斷演算法的復雜度，Merge Sort BU就是一個反例

比較Merge Sort和Merge Sort Bottom Up兩種排序演算法的性能效率,整體而言, 兩種演算法的效率是差不多的，但是如果進行仔細測驗, 自底向上的歸并排序會略勝一籌，

總體來說, Merge Sort BU 比 Merge Sort 快一些，但優化后, 二者的性能差距不明顯，

快速排序

// 對arr[l...r]部分進行partition操作
// 回傳p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
template <typename T>
int __partition(T arr[], int l, int r){

    T v = arr[l];

    int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
    for( int i = l + 1 ; i <= r ; i ++ )
        if( arr[i] < v ){
            j ++;
            swap( arr[j] , arr[i] );
        }

    swap( arr[l] , arr[j]);

    return j;
}

// 對arr[l...r]部分進行快速排序
template <typename T>
void __quickSort(T arr[], int l, int r){

    if( l >= r )
        return;

    int p = __partition(arr, l, r);
    __quickSort(arr, l, p-1 );
    __quickSort(arr, p+1, r);
}

template <typename T>
void quickSort(T arr[], int n){

    __quickSort(arr, 0, n-1);
}

比較Merge Sort和Quick Sort兩種排序演算法的性能效率,兩種排序演算法雖然都是O(nlogn)級別的, 但是Quick Sort演算法有常數級的優勢,Quick Sort要比Merge Sort快, 即使對Merge Sort進行了優化,是對于近乎有序的陣列, 快速排序演算法退化成了O(n^2)級別的演算法,下面對其進行優化

template <typename T>
int _partition(T arr[], int l, int r){

    // 隨機在arr[l...r]的范圍中, 選擇一個數值作為標定點pivot
    swap( arr[l] , arr[rand()%(r-l+1)+l] );

    T v = arr[l];
    int j = l;
    for( int i = l + 1 ; i <= r ; i ++ )
        if( arr[i] < v ){
            j ++;
            swap( arr[j] , arr[i] );
        }

    swap( arr[l] , arr[j]);

    return j;
}

// 對arr[l...r]部分進行快速排序
template <typename T>
void _quickSort(T arr[], int l, int r){

    // 對于小規模陣列, 使用插入排序進行優化
    if( r - l <= 15 ){
        insertionSort(arr,l,r);
        return;
    }

    int p = _partition(arr, l, r);
    _quickSort(arr, l, p-1 );
    _quickSort(arr, p+1, r);
}

template <typename T>
void quickSort(T arr[], int n){

    srand(time(NULL));
    _quickSort(arr, 0, n-1);
}

加入了隨機選擇標定點的步驟后, 我們的快速排序可以輕松處理近乎有序的陣列,但是對于近乎有序的陣列, 其效率比優化后的歸并排序要低, 但完全再容忍范圍里,但此時, 對于含有大量相同元素的陣列, 我們的快速排序演算法再次退化成了O(n^2)級別的演算法,

雙路快速排序

// 雙路快速排序的partition
// 回傳p, 使得arr[l...p-1] <= arr[p] ; arr[p+1...r] >= arr[p]
// 雙路快排處理的元素正好等于arr[p]的時候要注意，詳見下面的注釋：）
template <typename T>
int _partition2(T arr[], int l, int r){

    // 隨機在arr[l...r]的范圍中, 選擇一個數值作為標定點pivot
    swap( arr[l] , arr[rand()%(r-l+1)+l] );
    T v = arr[l];

    // arr[l+1...i) <= v; arr(j...r] >= v
    int i = l+1, j = r;
    while( true ){
        // 注意這里的邊界, arr[i] < v, 不能是arr[i] <= v
        while( i <= r && arr[i] < v )
            i ++;

        // 注意這里的邊界, arr[j] > v, 不能是arr[j] >= v
        while( j >= l+1 && arr[j] > v )
            j --;

        // 對于上面的兩個邊界的設定, 有的同學在課程的問答區有很好的回答:)

        if( i > j )
            break;

        swap( arr[i] , arr[j] );
        i ++;
        j --;
    }

    swap( arr[l] , arr[j]);

    return j;
}

// 對arr[l...r]部分進行快速排序
template <typename T>
void _quickSort(T arr[], int l, int r){

    // 對于小規模陣列, 使用插入排序進行優化
    if( r - l <= 15 ){
        insertionSort(arr,l,r);
        return;
    }

    // 呼叫雙路快速排序的partition
    int p = _partition2(arr, l, r);
    _quickSort(arr, l, p-1 );
    _quickSort(arr, p+1, r);
}

template <typename T>
void quickSort(T arr[], int n){

    srand(time(NULL));
    _quickSort(arr, 0, n-1);
}

雙路快速排序演算法也可以輕松處理近乎有序的陣列,使用雙快速排序后, 我們的快速排序演算法可以輕松的處理包含大量元素的陣列

三路快速排序(可以對比單路快速排序)

// 遞回的三路快速排序演算法
template <typename T>
void __quickSort3Ways(T arr[], int l, int r){

    // 對于小規模陣列, 使用插入排序進行優化
    if( r - l <= 15 ){
        insertionSort(arr,l,r);
        return;
    }

    // 隨機在arr[l...r]的范圍中, 選擇一個數值作為標定點pivot
    swap( arr[l], arr[rand()%(r-l+1)+l ] );

    T v = arr[l];

    int lt = l;     // arr[l+1...lt] < v
    int gt = r + 1; // arr[gt...r] > v
    int i = l+1;    // arr[lt+1...i) == v
    while( i < gt ){
        if( arr[i] < v ){
            swap( arr[i], arr[lt+1]);
            i ++;
            lt ++;
        }
        else if( arr[i] > v ){
            swap( arr[i], arr[gt-1]);
            gt --;
        }
        else{ // arr[i] == v
            i ++;
        }
    }

    swap( arr[l] , arr[lt] );

    __quickSort3Ways(arr, l, lt-1);
    __quickSort3Ways(arr, gt, r);
}

template <typename T>
void quickSort3Ways(T arr[], int n){

    srand(time(NULL));
    __quickSort3Ways( arr, 0, n-1);
}

比較Merge Sort和雙路快速排序和三路快排三種排序演算法的性能效率，對于包含有大量重復資料的陣列, 三路快排有巨大的優勢，對于一般性的隨機陣列和近乎有序的陣列, 三路快排的效率雖然不是最優的, 但是是在非常可以接受的范圍里，因此, 在一些語言中, 三路快排是默認的語言庫函式中使用的排序演算法，比如Java:)

逆序數對(歸并排序)

// 計算逆序數對的結果以long long回傳
// 對于一個大小為N的陣列, 其最大的逆序數對個數為 N*(N-1)/2, 非常容易產生整型溢位

// merge函式求出在arr[l...mid]和arr[mid+1...r]有序的基礎上, arr[l...r]的逆序數對個數
long long __merge( int arr[], int l, int mid, int r){

    int *aux = new int[r-l+1];
    for( int i = l ; i <= r ; i ++ )
        aux[i-l] = arr[i];

    // 初始化逆序數對個數 res = 0
    long long res = 0;
    // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
    int j = l, k = mid + 1;
    for( int i = l ; i <= r ; i ++ ){
        if( j > mid ){ // 如果左半部分元素已經全部處理完畢
            arr[i] = aux[k-l];
            k ++;
        }
        else if( k > r ){ // 如果右半部分元素已經全部處理完畢
            arr[i] = aux[j-l];
            j ++;
        }
        else if( aux[j-l] <= aux[k-l] ){ // 左半部分所指元素 <= 右半部分所指元素
            arr[i] = aux[j-l];
            j ++;
        }
        else{ // 右半部分所指元素 < 左半部分所指元素
            arr[i] = aux[k-l];
            k ++;
            // 此時, 因為右半部分k所指的元素小
            // 這個元素和左半部分的所有未處理的元素都構成了逆序數對
            // 左半部分此時未處理的元素個數為 mid - j + 1
            res += (long long)(mid - j + 1);
        }
    }

    delete[] aux;

    return res;
}

// 求arr[l..r]范圍的逆序數對個數
// 思考: 歸并排序的優化可否用于求逆序數對的演算法? :)
long long __inversionCount(int arr[], int l, int r){

    if( l >= r )
        return 0;

    int mid = l + (r-l)/2;

    // 求出 arr[l...mid] 范圍的逆序數
    long long res1 = __inversionCount( arr, l, mid);
    // 求出 arr[mid+1...r] 范圍的逆序數
    long long res2 = __inversionCount( arr, mid+1, r);

    return res1 + res2 + __merge( arr, l, mid, r);
}

// 遞回求arr的逆序數對個數
long long inversionCount(int arr[], int n){

    return __inversionCount(arr, 0, n-1);
}

尋找arr陣列中第k小的元素(快速排序)

main.cpp

#include <iostream>
#include <ctime>
#include <cassert>
#include <algorithm>
#include "TestHelper.h"

using namespace std;

// partition 程序, 和快排的partition一樣
template <typename T>
int __partition( T arr[], int l, int r ){

    int p = rand()%(r-l+1) + l;
    swap( arr[l] , arr[p] );

    int j = l; //[l+1...j] < p ; [lt+1..i) > p
    for( int i = l + 1 ; i <= r ; i ++ )
        if( arr[i] < arr[l] )
            swap(arr[i], arr[++j]);

    swap(arr[l], arr[j]);

    return j;
}

// 求出arr[l...r]范圍里第k小的數
template <typename T>
T __selection( T arr[], int l, int r, int k ){

    if( l == r )
        return arr[l];

    // partition之后, arr[p]的正確位置就在索引p上
    int p = __partition( arr, l, r );

    if( k == p )    // 如果 k == p, 直接回傳arr[p]
        return arr[p];
    else if( k < p )    // 如果 k < p, 只需要在arr[l...p-1]中找第k小元素即可
        return __selection( arr, l, p-1, k);
    else // 如果 k > p, 則需要在arr[p+1...r]中找第k-p-1小元素
         // 注意: 由于我們傳入__selection的依然是arr, 而不是arr[p+1...r],
         //       所以傳入的最后一個引數依然是k, 而不是k-p-1
        return __selection( arr, p+1, r, k );
}

// 尋找arr陣列中第k小的元素
// 注意: 在我們的演算法中, k是從0開始索引的, 即最小的元素是第0小元素, 以此類推
// 如果希望我們的演算法中k的語意是從1開始的, 只需要在整個邏輯開始進行k--即可, 可以參考selection2
template <typename T>
T selection(T arr[], int n, int k) {

    assert( k >= 0 && k < n );

    srand(time(NULL));
    return __selection(arr, 0, n - 1, k);
}

// 尋找arr陣列中第k小的元素, k從1開始索引, 即最小元素是第1小元素, 以此類推
template <typename T>
T selection2(T arr[], int n, int k) {

    return selection(arr, n, k - 1);
}


// 測驗 selection演算法
int main() {

    // 生成一個大小為n, 包含0...n-1這n個元素的隨機陣列arr
    int n = 10000;
    int* arr = TestHelper::generateOrderedArray(n);
    TestHelper::shuffleArray(arr, n);

    // 驗證selection演算法, 對arr陣列求第i小元素, 應該為i
    for( int i = 0 ; i < n ; i ++ ){
        assert( selection(arr, n, i) == i );
        cout<<"test "<<i<<" complete."<<endl;
    }
    cout<<"Test selection completed."<<endl;

    delete[] arr;

    cout << endl;

    // 驗證selection2演算法
    arr = TestHelper::generateOrderedArray(n);
    TestHelper::shuffleArray(arr, n);

    // 對arr陣列求第i小元素, 應該為i - 1 (在selection2中, 第k小元素的k是從1索引的)
    for( int i = 1 ; i <= n ; i ++ ){
        assert( selection2(arr, n, i) == i - 1 );
        cout<<"test "<<i<<" complete."<<endl;
    }
    cout<<"Test selection2 completed."<<endl;

    delete[] arr;

    return 0;
}

TestHelper.h


#ifndef OPTIONAL_3_SELECTION_TESTHELPER_H
#define OPTIONAL_3_SELECTION_TESTHELPER_H

#include <iostream>
#include <algorithm>
#include <ctime>

using namespace std;

namespace TestHelper {

    // 生成一個完全有序的陣列
    int *generateOrderedArray(int n) {

        int *arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = i;

        return arr;
    }

    // 將陣列arr隨機化
    void shuffleArray(int arr[], int n){

        srand(time(NULL));
        for (int i = 0; i < n; i++) {
            int j = rand() % (n-i)+i;
            swap( arr[i], arr[j]);
        }
    }
}
#endif //OPTIONAL_3_SELECTION_TESTHELPER_H

總結

Merge Sort BU 比 Merge Sort 快一些，但優化后, 二者的性能差距不明顯，

Shell Sort雖然慢于高級的排序方式, 但仍然是非常有競爭力的一種排序演算法，其所花費的時間完全在可以容忍的范圍內, 遠不像O(n^2)的排序演算法, 在資料量較大的時候無法忍受，同時, Shell Sort實作簡單, 只使用回圈的方式解決排序問題, 不需要實作遞回, 不占用系統占空間, 也不依賴亂數，所以, 如果演算法實作所使用的環境不利于實作復雜的排序演算法, 或者在專案工程的測驗階段, 完全可以暫時使用Shell Sort來進行排序任務:)

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/60077.html

標籤：其他

上一篇：CF1324E Sleeping Schedule（基礎dp）

下一篇：為什么作業系統能安裝到虛擬機

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 網閘典型架構簡述

    網閘架構一般分為兩種：三主機的三系統架構網閘和雙主機的2+1架構網閘。 三主機架構分別為內端機、外端機和仲裁機。三機無論從軟體和硬體上均各自獨立。首先從硬體上來看，三機都用各自獨立的主板、記憶體及存盤設備。從軟體上來看，三機有各自獨立的作業系統。這樣能達到完全的三機獨立。對于“2+1”系統，“2”分為 ......

    uj5u.com 2020-09-10 02:00:44 more
  • 如何從xshell上傳檔案到centos linux虛擬機里

    如何從xshell上傳檔案到centos linux虛擬機里及：虛擬機CentOs下執行 yum -y install lrzsz命令，出現錯誤：鏡像無法找到軟體包 前言 一、安裝lrzsz步驟 二、上傳檔案 三、遇到的問題及解決方案 總結 前言 提示：其實很簡單，往虛擬機上安裝一個上傳檔案的工具 ......

    uj5u.com 2020-09-10 02:00:47 more
  • 一、SQLMAP入門

    一、SQLMAP入門 1、判斷是否存在注入 sqlmap.py -u 網址/id=1 id=1不可缺少。當注入點后面的引數大于兩個時。需要加雙引號， sqlmap.py -u "網址/id=1&uid=1" 2、判斷文本中的請求是否存在注入 從文本中加載http請求，SQLMAP可以從一個文本檔案中 ......

    uj5u.com 2020-09-10 02:00:50 more
  • Metasploit 簡單使用教程

    metasploit 簡單使用教程 浩先生， 2020-08-28 16:18:25 分類專欄： kail 網路安全 linux 文章標簽： linux資訊安全 編輯 著作權 metasploit 使用教程 前言 一、Metasploit是什么？ 二、準備作業 三、具體步驟 前言 Msfconsole ......

    uj5u.com 2020-09-10 02:00:53 more
  • 游戲逆向之驅動層與用戶層通訊

    驅動層代碼： #pragma once #include <ntifs.h> #define add_code CTL_CODE(FILE_DEVICE_UNKNOWN,0x800,METHOD_BUFFERED,FILE_ANY_ACCESS) /* 更多游戲逆向視頻www.yxfzedu.com ......

    uj5u.com 2020-09-10 02:00:56 more
  • 北斗電力時鐘（北斗授時服務器）讓網路資料更精準

    北斗電力時鐘（北斗授時服務器）讓網路資料更精準 北斗電力時鐘（北斗授時服務器）讓網路資料更精準 京準電子科技官微——ahjzsz 近幾年，資訊技術的得了快速發展，互聯網在逐漸普及，其在人們生活和生產中都得到了廣泛應用，并且取得了不錯的應用效果。計算機網路資訊在電力系統中的應用，一方面使電力系統的運行 ......

    uj5u.com 2020-09-10 02:01:03 more
  • 【CTF】CTFHub 技能樹 彩蛋 writeup

    ?碎碎念 CTFHub：https://www.ctfhub.com/ 筆者入門CTF時時剛開始刷的是bugku的舊平臺，后來才有了CTFHub。 感覺不論是網頁UI設計，還是題目質量，賽事跟蹤，工具軟體都做得很不錯。 而且因為獨到的金幣制度的確讓人有一種想去刷題賺金幣的感覺。 個人還是非常喜歡這個 ......

    uj5u.com 2020-09-10 02:04:05 more
  • 02windows基礎操作

    我學到了一下幾點 Windows系統目錄結構與滲透的作用 常見Windows的服務詳解 Windows埠詳解 常用的Windows注冊表詳解 hacker DOS命令詳解（net user / type /md /rd/ dir /cd /net use copy、批處理 等） 利用dos命令制作 ......

    uj5u.com 2020-09-10 02:04:18 more
  • 03.Linux基礎操作

    我學到了以下幾點 01Linux系統介紹02系統安裝，密碼啊破解03Linux常用命令04LAMP 01LINUX windows： win03 8 12 16 19 配置不繁瑣 Linux：redhat,centos(紅帽社區版)，Ubuntu server,suse unix:金融機構，證券，銀 ......

    uj5u.com 2020-09-10 02:04:30 more
  • 05HTML

    01HTML介紹 02頭部標簽講解03基礎標簽講解04表單標簽講解 HTML前段語言 js1.了解代碼2.根據代碼 懂得挖掘漏洞 （POST注入/XSS漏洞上傳）3.黑帽seo 白帽seo 客戶網站被黑帽植入劫持代碼如何處理4.熟悉html表單 <html><head><title>TDK標題，描述 ......

    uj5u.com 2020-09-10 02:04:36 more
最新发布
  • 2023年最新微信小程式抓包教程

    01 開門見山 隔一個月發一篇文章，不過分。 首先回顧一下《微信系結手機號資料庫被脫庫事件》，我也是第一時間得知了這個訊息，然后跟蹤了整件事情的經過。下面是這起事件的相關截圖以及近日流出的一萬條資料樣本： 個人認為這件事也沒什么，還不如關注一下之前45億快遞資料查詢渠道疑似在近日復活的訊息。 訊息是 ......

    uj5u.com 2023-04-20 08:48:24 more
  • web3 產品介紹：metamask 錢包 使用最多的瀏覽器插件錢包

    Metamask錢包是一種基于區塊鏈技術的數字貨幣錢包，它允許用戶在安全、便捷的環境下管理自己的加密資產。Metamask錢包是以太坊生態系統中最流行的錢包之一，它具有易于使用、安全性高和功能強大等優點。 本文將詳細介紹Metamask錢包的功能和使用方法。 一、 Metamask錢包的功能 數字資 ......

    uj5u.com 2023-04-20 08:47:46 more
  • vulnhub_Earth

    前言 靶機地址->>>vulnhub_Earth 攻擊機ip：192.168.20.121 靶機ip：192.168.20.122 參考文章 https://www.cnblogs.com/Jing-X/archive/2022/04/03/16097695.html https://www.cnb ......

    uj5u.com 2023-04-20 07:46:20 more
  • 從4k到42k，軟體測驗工程師的漲薪史，給我看哭了

    清明節一過，盲猜大家已經無心上班，在數著日子準備過五一，但一想到銀行卡里的余額……瞬間心情就不美麗了。最近，2023年高校畢業生就業調查顯示，本科畢業月平均起薪為5825元。調查一出，便有很多同學表示自己又被平均了。看著這一資料，不免讓人想到前不久中國青年報的一項調查：近六成大學生認為畢業10年內會 ......

    uj5u.com 2023-04-20 07:44:00 more
  • 最新版本 Stable Diffusion 開源 AI 繪畫工具之中文自動提詞篇

    🎈 標簽生成器 由于輸入正向提示詞 prompt 和反向提示詞 negative prompt 都是使用英文，所以對學習母語的我們非常不友好 使用網址：https://tinygeeker.github.io/p/ai-prompt-generator 這個網址是為了讓大家在使用 AI 繪畫的時候 ......

    uj5u.com 2023-04-20 07:43:36 more
  • 漫談前端自動化測驗演進之路及測驗工具分析

    隨著前端技術的不斷發展和應用程式的日益復雜，前端自動化測驗也在不斷演進。隨著 Web 應用程式變得越來越復雜，自動化測驗的需求也越來越高。如今，自動化測驗已經成為 Web 應用程式開發程序中不可或缺的一部分，它們可以幫助開發人員更快地發現和修復錯誤，提高應用程式的性能和可靠性。 ......

    uj5u.com 2023-04-20 07:43:16 more
  • CANN開發實踐：4個DVPP記憶體問題的典型案例解讀

    摘要：由于DVPP媒體資料處理功能對存放輸入、輸出資料的記憶體有更高的要求（例如，記憶體首地址128位元組對齊），因此需呼叫專用的記憶體申請介面，那么本期就分享幾個關于DVPP記憶體問題的典型案例，并給出原因分析及解決方法。 本文分享自華為云社區《FAQ_DVPP記憶體問題案例》，作者：昇騰CANN。 DVPP ......

    uj5u.com 2023-04-20 07:43:03 more
  • msf學習

    msf學習 以kali自帶的msf為例 一、msf核心模塊與功能 msf模塊都放在/usr/share/metasploit-framework/modules目錄下 1、auxiliary 輔助模塊，輔助滲透（埠掃描、登錄密碼爆破、漏洞驗證等） 2、encoders 編碼器模塊，主要包含各種編碼 ......

    uj5u.com 2023-04-20 07:42:59 more
  • Halcon軟體安裝與界面簡介

    1. 下載Halcon17版本到到本地 2. 雙擊安裝包后 3. 步驟如下 1.2 Halcon軟體安裝 界面分為四大塊 1. Halcon的五個助手 1) 影像采集助手：與相機連接，設定相機引數，采集影像 2) 標定助手：九點標定或是其它的標定，生成標定檔案及內參外參，可以將像素單位轉換為長度單位 ......

    uj5u.com 2023-04-20 07:42:17 more
  • 在MacOS下使用Unity3D開發游戲

    第一次發博客，先發一下我的游戲開發環境吧。 去年2月份買了一臺MacBookPro2021 M1pro(以下簡稱mbp)，這一年來一直在用mbp開發游戲。我大致分享一下我的開發工具以及使用體驗。 1、Unity 官網鏈接： https://unity.cn/releases 我一般使用的Apple ......

    uj5u.com 2023-04-20 07:40:19 more

Copyright © 2010-2020 有解無憂