1. 冒泡排序

冒泡排序重復地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果他們的順序（如從大到小、首字母從A到Z）錯誤就把他們交換過來。走訪元素的工作是重復地進行直到?jīng)]有相鄰元素需要交換，也就是說該元素已經(jīng)排序完成。

1.1 解題步驟

1.比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
2.針對所有的元素重復以上的步驟，除了最后一個；

1.2 復雜度和穩(wěn)定性

• 平均時間復雜度：O(n^2)
• 最壞時間復雜度：O(n^2)
• 最好時間復雜度：O(n)
• 空間復雜度：O(1)
• 穩(wěn)定性：穩(wěn)定排序

1.3 代碼

void bubbleSort(vector<int> &nums){
    for(int i=0;i<nums.size()-1;i++){
        for(int j=0;j<nums.size()-i-1;j++){
          if(nums[j]>nums[j+1]){
                int temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
          }
       }
    }
}

2.選擇排序

選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素排完。 選擇排序是不穩(wěn)定的排序方法。

2.1 解題步驟

1.假設排序表為 L[1....n]
2.第i趟排序即從L[i,,,,n] 中選擇關鍵字最小的元素與 L(i) 交換，每一趟排序可以確定一個元素的最終位置，這樣經(jīng)過 n-1 趟排序就可以使整個排序表有序。

2.2 復雜度和穩(wěn)定性

• 平均時間復雜度：O(n^2)
• 最壞時間復雜度：O(n^2)
• 最好時間復雜度：O(n^2)
• 空間復雜度：O(1)
• 穩(wěn)定性：不穩(wěn)定排序

2.3 代碼

void selectSort(vector<int> &nums){
    for(int i=0;i<nums.size()-1;i++){
        int temp=i;
        for(int j=i+1;j<nums.size();j++){
            if(nums[j]<nums[temp]) temp = j;
        }
        swap(nums[temp], nums[i]);
    }
}

3.插入排序

插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序。

3.1 解題步驟

1.從第一個元素開始，該元素可以認為已經(jīng)被排序；
2.取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描直到從已排序序列中找到比新元素小或者等的元素（t）；
3.將新元素插入在這個元素（t）后面。

3.2 復雜度和穩(wěn)定性

• 平均時間復雜度：O(n^2)
• 最壞時間復雜度：O(n^2)
• 最好時間復雜度：O(n)
• 空間復雜度：O(1)
• 穩(wěn)定性：穩(wěn)定排序

3.3 代碼

void insertSort(vector<int> &nums){
    for(int j=1; j<nums.size(); j++){
        int temp = nums[j];
        int i = j-1;
        while(i>=0 && nums[i]>temp){
            nums[i+1] = nums[i];
            i = i-1;
        }
        nums[i+1] = temp;
    }
}

4.歸并排序

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

4.1 解題步驟

1.把輸入序列分成子序列；
2.對這兩個子序列分別采用歸并排序；
3.將兩個排序好的子序列合并成一個最終的排序序列。

4.2 復雜度和穩(wěn)定性

• 平均時間復雜度：O(nlogn)
• 最壞時間復雜度：O(nlogn)
• 最好時間復雜度：O(nlogn)
• 空間復雜度：O(n)
• 穩(wěn)定性：穩(wěn)定排序

4.3 代碼

void _merge(vector<int> &nums, int left, int med, int right){
    vector<int> L(nums.begin()+left, nums.begin()+med+1);
    vector<int> R(nums.begin()+med+1, nums.begin()+right+1);

    // 設置哨兵  簡化代碼  不用每次判斷數(shù)組是否為空
    L.push_back(INT_MAX);
    R.push_back(INT_MAX);
    int i=0, j=0;

    for(int k=left; k<=right; k++){
        if(L[i] < R[j]){
            nums[k] = L[i];
            i++;
        }else{
            nums[k] = R[j];
            j++;
        }
    }
}

void _sort(vector<int> &nums, int left, int right){
    int med = (left+right)/2;
    if(left < right){
        _sort(nums, left, med);
        _sort(nums, med+1, right);
        _merge(nums, left, med, right);
    }
}

void mergeSort(vector<int> &nums){
    _sort(nums, 0, nums.size()-1);
}

5.快速排序

快速排序（Quicksort）是對冒泡排序的一種改進。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。

5.1 解題步驟

1.選取最后一個元素值作為基準值，使得左邊的數(shù)比當前值小，右邊的數(shù)比當前值大；
2.創(chuàng)建兩個數(shù)組下標，一個為 cur記錄當前數(shù)字，一個為pre記錄cur的前一個數(shù)字；
3.如果cur的數(shù)字大于基準值，pre不動，cur++；如果cur的數(shù)字小于基準值則交換cur和pre的數(shù)字，cur++,pre++；
4.交換基準值和pre的數(shù)字。

5.2 復雜度和穩(wěn)定性

• 平均時間復雜度：O(nlogn)
• 最壞時間復雜度：O(n^2)
• 最好時間復雜度：O(nlogn)
• 空間復雜度：O(nlogn)
• 穩(wěn)定性：不穩(wěn)定排序

5.3 遞歸實現(xiàn)

int partition_(vector<int>& nums, int p, int r){
    int base = nums[r];
    int pre=p;
    for(int cur=pre;cur<r;cur++){
        if(nums[cur]<=base){
            if(pre!=cur) swap(nums[pre], nums[cur]);
            pre++;
        }
    }
    swap(nums[pre], nums[r]);
    return pre;
}
void quickSort(vector<int>& nums, int p, int r){
    if(p<r){
        int q = partition_(nums, p, r);
        quickSort(nums, p, q-1);
        quickSort(nums, q+1, r);
    }
}

5.4 非遞歸實現(xiàn)

int partition_(vector<int>& nums, int p, int r){
    int base = nums[r];
    int pre=p;
    for(int cur=pre;cur<r;cur++){
        if(nums[cur]<=base){
            if(pre!=cur) swap(nums[pre], nums[cur]);
            pre++;
        }
    }
    swap(nums[pre], nums[r]);
    return pre;
}

void quickSort_(vector<int>& nums, int p, int r){
    stack<int> s;
    s.push(p);
    s.push(r);
    int left,right;

    while(!s.empty()){
        right = s.top();
        s.pop();
        left = s.top();
        s.pop();

        if(left<right){
            int q = partition_(nums, left, right);
            s.push(left);
            s.push(q-1);
            s.push(q+1);
            s.push(right);
        }
    }
}

6.堆排序

堆排序是利用堆這種數(shù)據(jù)結構而設計的一種排序算法，堆排序是一種選擇排序。

6.1 解題步驟

參考 https://www.cnblogs.com/chengxiao/p/6129630.html

1. 將無需序列構建成一個堆，根據(jù)升序降序需求選擇大頂堆或小頂堆;
2. 將堆頂元素與末尾元素交換，將最大元素"沉"到數(shù)組末端;
3. 重新調(diào)整結構，使其滿足堆定義，然后繼續(xù)交換堆頂元素與當前末尾元素，反復執(zhí)行調(diào)整+交換步驟，直到整個序列有序。

6.2 復雜度和穩(wěn)定性

• 平均時間復雜度：O(nlogn)
• 最壞時間復雜度：O(nlogn)
• 最好時間復雜度：O(nlogn)
• 空間復雜度：O(1)
• 穩(wěn)定性：不穩(wěn)定排序

6.3 代碼

void maxHeap(vector<int> &nums, int i, int high){
    int left = 2*i+1, right = 2*i+2;
    int largest;
    if(left<high&&nums[left]>nums[i]) largest = left;
    else largest = i;

    if(right<high&&nums[right]>nums[largest]) largest = right;

    if(largest!=i){
        swap(nums[i], nums[largest]);
        maxHeap(nums, largest, high);
    }

}

void bulidHeap(vector<int> &nums){
    for(int i=nums.size()/2-1; i>=0; i--){
        maxHeap(nums, i, nums.size());
    }
}

void heapSort(vector<int> &nums){
    bulidHeap(nums);
    for(int i=nums.size()-1; i>0; i--){
        swap(nums[0], nums[i]);
        maxHeap(nums, 0, i);
    }
}

int main()
{
    vector<int> nums = {16, 4, 10, 14, 7, 9, 3, 2, 8, 1};
    heapSort(nums);
    for(auto num:nums){
        cout << num << " ";
    }
    cout << endl;
    return 0;
}