排序算法

插入排序.gif 选择排序.gif 归并排序.gif 快排.gif 双下标快排.png

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    // 冒泡排序
    vector<int> bubbleSort(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++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;
                }
            }
        }
        return nums;
    }

    /**
        插入排序
     以i为分界线，i左边的为已排区域，i以及i右边的为未排区域，每次拿i的值与前面的值相比较，以j定位与nums[i]对比的值，当未找到合适时则将nums[j]右移一位，直到查到比nums[i]小的值或者当j为-1时插入nums[i],
     */
    vector<int> insertionSort(vector<int>& nums) {
        if (nums.size() <= 1) return nums;
        for (int i = 0; i < nums.size(); i++) {
            int value = nums[i];
            int j = i - 1;
            for (; j>= 0; j--) {    //逆查找适合位置
                if (nums[j] > value) {
                    nums[j + 1] = nums[j]; // 当未找到合适时则将nums[j]右移一位
                }else {
                    break;  //找到合适位置时暂停循环
                }
            }
            nums[j + 1] = value;    //找到合适位置进行插入操作
        }
        return nums;
    }
    
    /**
        选择排序
     先遍历出未排序数据找出最小值与已排序末尾的数据进行替换，i左侧为已排序数据，右侧为未排序数据，通过遍历未排序段进行最小数据查找并与nums[i]进行替换从而得到有序的数列
     */
    vector<int> selectSort(vector<int>& nums) {
        if (nums.size() <= 1) return nums;
        for (int i = 0; i < nums.size(); i++) {
            int val = nums[i];
            int index = i;
            for (int j = i; j < nums.size(); j++) {
                if (nums[j] < val) {
                    val = nums[j];
                    index = j;
                }
            }
            
            nums[index] = nums[i];
            nums[i] =  val;
            
            /**
             //通过位移插入数据
             for (int a = index; a > i; a--) {
                 nums[a] = nums[a - 1];
             }
             nums[i] = val;
             */
        }
        return nums;
    }
    
    /**
        归并排序
            生成一个与原数组相同大小的数组便于存储正在进行排序的数据， 递归时将数组进行分割排序并对排序好的数据进行合并调用；合并方法中通过i、j左右指针指向左右数组中对应的排序数据下标，当当前数组排序结束后再将值copy到原数组中,其时间复杂度为O(nlogn),空间复杂度为O(n).
     参考:https://www.jianshu.com/p/33cffa1ce613
     */
       
    void sort(vector<int> &nums) {
        vector<int> temp = nums; //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        sort(nums, 0, (int)(nums.size() - 1), temp);
    }
    
    void sort(vector<int> &nums, int left, int right, vector<int>temp) {
        if (left < right) {
            long mid = (left + right) / 2;
            
            sort(nums, left, int(mid), temp); //左边归并排序，使得左子序列有序
            sort(nums, int(mid + 1), right, temp);//右边归并排序，使得右子序列有序
            
            // 递归调用上面的代码调用结束直至left>right才会执行递归中的如下代码
            // left为左侧下标值， right为右侧下标值
            merge(nums, left, int(mid), right, temp);//将两个有序子数组合并操作
        }
    }
    
    void merge(vector<int> &nums, int left, int mid, int right, vector<int> temp) {
        int i = left;//左序列指针
        int j = mid + 1;//右序列指针
        int t = 0;//临时数组指针
        
        while (i <= mid && j <= right) {// 对左右数组的下标进行大小限制
            if (nums[i] <= nums[j]) {   // 对左右数组对应下标下的值进行比较,并取出教小的值放到temp中
                temp[t++] = nums[i++];
            }else {
                temp[t++] = nums[j++];
            }
        }
        while (i <= mid) { //将左边剩余元素填充进temp中
            temp[t++] = nums[i++];
        }
        while (j <= right) {//将右序列剩余元素填充进temp中
            temp[t++] = nums[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while (left <= right) {
            nums[left++] = temp[t++];
        }
    }

    /**
        快速排序双下标实现
     参考：https://blog.csdn.net/starzyh/article/details/90272347
     */
    void quickSort(vector<int> &nums, int left, int right)
    {
        if(left < right)
        {
            // 存储当前第一个值并取出该值以进行后期的对比
            int pivot = nums[left];
            // 设置双标，low记录当前将要被插入的下标(也是当前获取的privot的下标)
            int low = left, high = right;
            while(low < high) // 分为两个下标向中间移动，当两下标相遇时将pivot的值插入
            {
                while(nums[high] >= pivot && low < high){   //如果高位值大于pivot则获取前一个值再进行比较
                   high--;
                }
                // 获取到的nums[high]比pivot则将该值赋值给nums[low],
                // 拟定当前的high为 high1，以便后面理解，在执行该循环下面的代码时high将不会再发生改变
                nums[low] = nums[high];
                while(nums[low] <= pivot && low < high){ //如果获取的低位值小于pivot则进行++进入下个循环
                   low++;
                }
                // 获取到的nums[low]比pivot大，此时将nums[low]的数值赋值给nums[high],即nums[high1],此时的high1==high
                nums[high] = nums[low];
            }
            // 遍历结束将当前pivot插入到nums[low]的位置，此时nums[low]左边的都小于pivot,右边的都大于pivot
            nums[low] = pivot;
            
            for (int i = 0; i < nums.size(); i++) {
                cout << nums[i] << "->";
            }
            cout << " " << endl;
            
            //递归对两边的数据继续进行排序
            quickSort(nums, left, low - 1);
            quickSort(nums, low + 1, right);
        }
    }
    
    
};

int main(int argc, const char * argv[]) {
    
    /**
     对于排序算法执行效率的分析，我们一般会从这几个方面来衡量：
    1.最好情况、最坏情况、平均情况时间复杂度
        我们在分析排序算法的时间复杂度时，要分别给出最好情况、最坏情况、平均情况下的时间复杂度。除此之外，你还要说出最好、最坏时间复杂度对应的要排序
        的原始数据是什么样的。
        为什么要区分这三种时间复杂度呢？第一，有些排序算法会区分，为了好对比，所以我们最好都做一下区分。第二，对于要排序的数据，有的接近有序，有的完
        全无序。有序度不同的数据，对于排序的执行时间肯定是有影响的，我们要知道排序算法在不同数据下的性能表现。
    2.时间复杂度的系数、常数 、低阶
        我们知道，时间复杂度反应的是数据规模n很大的时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中，我们排序的可能
        是10个、100个、1000个这样规模很小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。
    3.比较次数和交换（或移动）次数
        这一节和下一节讲的都是基于比较的排序算法。基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，如
        果我们在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。
     */
    
    vector<int> list = {4, 3, 6, 2, 7 , 8, 1, 5};
    Solution solution;
    solution.quickSort(list, 0, int(list.size() - 1));
    for (int i = 0; i < list.size(); i++) {
        printf("%d-", list[i]);
    }
    return 0;
}

参考：https://www.jianshu.com/p/33cffa1ce613
https://blog.csdn.net/starzyh/article/details/90272347
以及王铮老师的《数据结构与算法之美》