排序算法学习记录

排序在很多场合中都经常用到，排序算法属于很常用的算法之一，在此对几种经典的排序算法进行简单的讲解，主要包括简单排序中的选择排序，冒泡排序，插入排序，以及快排，归并排序，希尔排序等。

选择排序的主要思想是先从所有的元素中选取一个最小的元素，与最左边的数进行位置交换，然后从第二个元素到最后一个元素中再取一个最小的元素，与左边第二个数进行交换，依次循环下去。

vector Select_Sort(vectornums) {
    int min_value = INT_MAX, min_index = 0;
    int len = nums.size();
    for (int i = 0; i < len; i++) {
        min_value = INT_MAX;
        for (int j = i; j < len; j++) {
            if (nums[j] < min_value) {
                min_value = nums[j];//记录最小值
                min_index = j;//记录最小值的位置
            }
        }
        swap(nums[i], nums[min_index]);//将最小值移至左边
    }
    return nums;
}

时间复杂度：O(n^2),空间复杂度：O(1)

类似于冒泡的原理，将一个元素与后续元素依次作比较，若满足条件则进行位置交换，使得该元素逐渐向后移。

vectorBubble_Sort(vectornums) {
    int len = nums.size();
    for (int i = nums.size()-1; i>0; i--) {
        for (int j = 0; j  nums[j+1])swap(nums[j], nums[j+1]);
        }
    }
    return nums;
}

时间复杂度：O(n^2)，空间复杂度：O(1)

插入排序的思想是不断使前面一部分元素保持有序状态。假定前a个元素为有序状态，需要插入第a+1个元素，将第a+1个元素依次与前a个元素进行比较，并在合适的位置的进行插入，使a+1个元素保持有序。

vectorInsert_Sort(vectornums) {
    int len = nums.size();
    for (int i =1; i< nums.size() ; i++) {
        for (int j = i; j>0; j--) {
            if (nums[j] < nums[j - 1])swap(nums[j], nums[j - 1]);
        }
    }
    return nums;
}

时间复杂度：O(n^2)，空间复杂度：O(1)

归并排序用到了递归及合并两个操作，合并操作主要是将左右两边均有序的数组变成一个有序的数组，而递归操作是不断重复上述过程，不断合并数组，最终使所有元素变成有序。

void Merge(vector&nums, int leftptr, int rightptr, int rightbound) {
    vectortemp(rightbound - leftptr + 1, 0);
    int i = leftptr, j = rightptr, k = 0;
    int mid = rightptr - 1;
    while (i <= mid && j <= rightbound) {
        temp[k++] = nums[i] < nums[j] ? nums[i++]:nums[j++];
    }
    while (i <= mid)temp[k++] = nums[i++];
    while (j <= rightbound)temp[k++] = nums[j++];
    //将排好序的元素放入nums中
    for (int m = 0; m < temp.size(); m++) {
        nums[m + leftptr] = temp[m];
    }
}
void TS(vector&nums, int left, int right) {
    //递归终止条件
    if (left == right)return;
    //对序列进行切分
    int mid = left + (right - left) / 2;
    //对左边进行排序
    TS(nums,left, mid);
    //对右边进行排序
    TS(nums, mid + 1, right);
    //对排好序的左右两边进行合并
    Merge(nums,left,mid+1,right);
}
vectorMergetSort(vector&nums) {
    TS(nums, 0, nums.size()-1);
    return nums;
}

时间复杂度：O(n*log(n)) 空间复杂度：O(n)

是优化的选择排序，每取一个间隔gap的所有元素进行排序

vectorShell_Sort(vectornums) {
    //选择最优gap长度
    int h = 1;
    while (h <= nums.size() / 3) {
        h = h * 3 + 1;
    }
    for (int gap = h; gap > 0; gap =(gap-1)/3) {
        for (int i = gap; i < nums.size(); i++) {
            for (int j = i; j > gap-1; j -= gap) {
                if (nums[j] < nums[j - gap])swap(nums[j], nums[j - gap]);
            }
        }
    }
    return nums;
}

时间复杂度：O(n^1.3) 空间复杂度：O(1)

int get_pivot(vector& nums, int left,int right) {
    int pivot = right;
    int i = left, j = right - 1;
    while (i <= j) {
        while (i <= j && nums[i] <= nums[pivot])i++;
        while (i <= j && nums[j] > nums[pivot])j--;
        if (i <= j)swap(nums[i++], nums[j--]);
    }
    swap(nums[i], nums[pivot]);
    return i;
}

void Sort(vector& nums,int left,int right) {
    if (left >= right)return;
    int rand_position = left + rand() % (right - left);
    swap(nums[rand_position], nums[right]);
    int pivot = get_pivot(nums, left, right);
    Sort(nums, left, pivot - 1);
    Sort(nums, pivot + 1, right);
}
vectorQuickSort(vector&nums) {
    Sort(nums,0, nums.size() - 1);
    return nums;
}

时间复杂度：O(n*log(n)) 空间复杂度：O(log(n))

#include 
#include //要使用vector必须包含vector头文件
#include//产生随机数的rand包含在此头文件中
#include
using namespace std;

//data_cheker对数器
vectorGeneration() {
    int len = 1000;
    vectornums;
    for (int i = 0; i < len; i++) {
        nums.push_back(rand());
    }
    return nums;
}

int main()
{
    int times = 1000;
    bool result = true;
    while (times > 0) {
        vectornums1 = Generation();
        vectornums2 = nums1;
        sort(nums1.begin(), nums1.end());
        nums2 = QuickSort(nums2);//修改相应的排序算法名称即可
        for (int i = 0; i < nums2.size(); i++) {
            if (nums1[i] != nums2[i]) {
                result = false;
                break;
            }
        }
        if (result == false)break;
        times--;
    }
    if (result == false)cout << "算法不正确" << endl;
    else cout << "测试案例全部通过。" << endl;
    return 0;
}