選擇排序/插入排序/冒泡排序

選擇排序

首先在這整個陣列范圍里找到最小的元素1，然后和第一名的位置交換，之后我們在剩下的部分再找最小的元素2，把2和第二名的位置來交換，以此類推，

selectionSort

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[minIndex] > arr[j]) {
                minIndex = j;
            }
        }
        std::swap(arr[i], arr[minIndex]);
    }
}

優化

// 在每一輪中, 可以同時找到當前未處理元素的最大值和最小值
template<typename T>
void selectionSort(T arr[], const 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]) {
            std::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;
            }
        }
        std::swap(arr[left], arr[minIndex]);
        std::swap(arr[right], arr[maxIndex]);
        left++;
        right--;
    }
}

插入排序

對于第一個元素我們不動，因為當我們只考慮8這個元素是它已經是有序的了，我們要看的是6這個元素，對于這個元素我們要的是把它放到前面合適的位置，跟它前面的8相比6比8小索引它們要調換一下位置，此時前兩個元素就有序了，以此類推，

insertionSort

 //插入排序
template<typename T>
void insertionSort(T arr[], const 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) {
            std::swap(arr[j], arr[j - 1]);
        }
    }
}

優化交換為賦值

首先對于第零個元素8保持不變，然后考察6，先把6賦值一份，然后看看6是不是適合放在當前的位置，就和前面的元素做比較，如果和前一元素要小就說明不應該放在當前的這個位置，而8因該放在當前的這個位置，所以把8向后挪一位，之后再考察6是不是因該放在前一位置，以此類推，

• 如此對于近乎有序的序列插入排序非常高效，以至于相比較O(nlogn)級別的演算法還要快，在一個完全有序的陣列中，他會進化成一個O(n)級別的演算法，所以插入排序常用于演算法的優化中，

 //插入排序
template<typename T>
void insertionSort(T arr[], const int n) {
    for (int i = 1; i < n; i++) {
        // 尋找元素arr[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;
    }
}

冒泡排序

bubbleSort

//冒泡排序
template<typename T>
void bubbleSort(T arr[], const int n) {
   for (int i = 0; i < n - 1; ++i) {
       for (int j = 0; j < n - i - 1; ++j) {
           if (arr[j] > arr[j + 1]) {
               std::swap(arr[j], arr[j + 1]);
           }
       }
   }
}

優化

//優化
template<typename T>
void bubbleSort(T arr[], const int n) {
  bool isSwapped;
   int lastSwap = 0;
   int k = n - 1;
   for (int i = 0; i < n; ++i) {
   		//記錄當某一一輪是否發生交換行為，若為發生則判定已經排序成功，跳出回圈即可，
       isSwapped = false;
       for (int j = 0; j < k; ++j) {
           if (arr[j] > arr[j + 1]) {
               arr[j] = arr[j] ^ arr[j + 1];
               arr[j + 1] = arr[j + 1] ^ arr[j];
               arr[j] = arr[j] ^ arr[j + 1];
               isSwapped = true;
               /*記錄一輪交換后的最終索引，通過觀察發現這個索引后的數字都是有序的，
                     * 那么以后就不用比較這個索引后面的數字，即內層回圈的邊界是前面所說的最終索引，
                     * 當這個最終索引為0的時候（即前面沒有數字的時候）排序就結束了，
               	* */
               lastSwap = j;
           }
       }
       if (!isSwapped) break;
       k = lastSwap;
   }
}

概括

標籤：其他

上一篇：黑灰產眼中的NFT：平臺嗷嗷待宰，用戶送錢上門

下一篇：【Unity Shader學習筆記】Unity光照-陰影