排序算法 C++实现

一、插入排序 （Insertion Sort）

void insertion_sort(vector<int>& number){
    int length = number.size();
    if(length <= 1) return;
    
    for(int index = 1; index < length; ++index){
        int temp = number[index];
        int compare = index;
        for(; compare > 0 && temp < number[compare-1]; compare--)
            number[compare] = number[compare-1];
        number[compare] = temp;
    }
}

 

二、 快速排序（Quick Sort）

void quick_sort(vector<int>& number, int begin, int end){

    if(begin >= end) return;
    int mid = (begin+end)/2, pivot = number[mid];
    swap(number[mid], number[end]);
    
    int temp = begin - 1;
    for(int i = begin; i < end; i++)
        if(number[i] <= pivot)
            swap(number[++temp], number[i]);
    swap(number[++temp], number[end]);
    
    quick_sort(number, begin, temp-1);
    quick_sort(number, temp+1, end);
}

 

 三、归并排序（Merge Sort）

void MergeSort(vector<int>& number){
    vector<int> temp(number.size());
    mergesort(number, temp, 0, number.size()-1);
    //number.swap(temp);
}

void mergesort(vector<int>& number, vector<int>& temp, int begin, int end){
    if(begin < end){
        int center = (begin + end)/2;
        mergesort(number, temp, begin, center);
        mergesort(number, temp, center+1, end);
        merge(number, temp, begin, center+1, end);
    }
}
    
void merge(vector<int>& number, vector<int>& temp, int left, int right, int end){
    int leftend = right - 1;
    int tmpIndex = left;
    int total = end - left + 1;
    while(left <= leftend && right <= end){
        if(number[left] < number[right])
            temp[tmpIndex++] = number[left++];
        else
            temp[tmpIndex++] = number[right++];
    }
    
    while(left <= leftend)
        temp[tmpIndex++] = number[left++];
    
    while(right <= end)
        temp[tmpIndex++] = number[right++];
        
    for(int i = 0; i < total; ++i, --end)
        number[end] = temp[end];
}

 

 

示例代码：

#include <iostream>
#include <vector>

using namespace std;

void MergeSort(vector<int>&);
void mergesort(vector<int>&, vector<int>&, int, int);
void merge(vector<int>&, vector<int>&, int, int, int);

int main()
{
    vector<int> numbers = {34,8,64,51,21,1,23,45,90,540,47,35,70,134,152,251};
    // 1 8 21 23 34 35 45 47 51 64 70 90 134 152 251 540
    
    // insertion_sort(numbers);
    // quick_sort(numbers, 0, numbers.size()-1);
    MergeSort(numbers);
    for(int num : numbers)
        cout << num << ' ' ;
    return 0;
}