八大排序

八大排序

 

1.冒泡排序

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n=nums.size();
        int flag=0;
        for(int i=0;i<n-1;n--){
            for(int j=0;j<n-1;j++){
                if(nums[j]>nums[j+1]){
                   swap(nums[j],nums[j+1]);
                   flag=1;
                }
            }
            if(flag==0)break;
        }
        return nums;
    }
};

​

2.插入排序

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n=nums.size();
       for(int i=0;i<n-1;i++){
           int end=i;
           int x=nums[end+1];
           while(end>=0){
               if(nums[end]>x){
                   nums[end+1]=nums[end];
                   end--;
               }
               else break;//前面都是已经排好顺序的元素一个小个个小
           }
           nums[end+1]=x;
       }
       return nums;
    }
};

​

​

3.希尔排序(缩小增量算法)

基本思想：

先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的元素进行排序。

然后将gap逐渐减小重复上述分组和排序的工作。

当到达gap=1时，所有元素在统一组内排好序。

静态图演示：

其实就是多次插入排序。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n=nums.size();
        int gap=n;
        while(gap>1){
            gap=gap/3+1;
            for(int i=0;i<n-gap;i++){
                int end=i;
                int x=nums[end+gap];
                while(end>=0){
                    if(nums[end]>x){
                        nums[end+gap]=nums[end];
                        end-=gap;
                    }
                    else break;
                }
                nums[end+gap]=x;
            }
        }
        return nums;
    }
};

4.选择排序

基本思想：

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始(末尾)位置，

然后选出次小(或次大)的一个元素，存放在最大(最小)元素的下一个位置，

重复这样的步骤直到全部待排序的数据元素排完 。

动图演示：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n=nums.size();
        int begin=0,end=n-1;
        while(begin<end){
            int min=begin;
            int max=begin;
            for(int i=begin;i<=end;i++){
                if(nums[i]<nums[min]) min=i;
                if(nums[i]>nums[max]) max=i;
            }
            swap(nums[min],nums[begin]);
            //如果最大值一开始在起始位置
            if(begin==max)max=min;
            swap(nums[max],nums[end]);
            begin++;
            end--;
        }   
        return nums;
    }
};

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好(不论数组是否有序都会执行原步骤)。实际中很少使用

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)

4. 稳定性：不稳定

5.选择排序(堆排序) 1、首先了解堆是什么

堆是一种数据结构，一种叫做完全二叉树的数据结构。

2、堆的性质

这里我们用到两种堆，其实也算是一种。

大顶堆：每个节点的值都大于或者等于它的左右子节点的值。

小顶堆：每个节点的值都小于或者等于它的左右子节点的值。

如上所示，就是两种堆。

如果我们把这种逻辑结构映射到数组中，就是下边这样

95823471                 13542897                

这个数组arr逻辑上就是一个堆。

从这里我们可以得出以下性质（重点）

对于大顶堆：arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]

对于小顶堆：arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]

3、堆排序的基本思想

了解了以上内容，我们可以开始探究堆排序的基本思想了。

堆排序的基本思想是：1、将带排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素；2、将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆；3、重复步骤2，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了。

假设给定的无序序列arr是：

​ 4 5 8 2 3 9 7 1

1. 将无序序列构建成一个大顶堆。

   首先我们将现在的无序序列看成一个堆结构，一个没有规则的二叉树，将序列里的值按照从上往下，从左到右依次填充到二叉树中。

   ​

45923871                

根据大顶堆的性质，每个节点的值都大于或者等于它的左右子节点的值。所以我们需要找到所有包含子节点的节点，也就是非叶子节点，然后调整他们的父子关系，非叶子节点遍历的顺序应该是从下往上，这比从上往下的顺序遍历次数少很多，因为，大顶堆的性质要求父节点的值要大于或者等于子节点的值，如果从上往下遍历，当某个节点即是父节点又是子节点并且它的子节点仍然有子节点的时候，因为子节点还没有遍历到，所以子节点不符合大顶堆性质，当子节点调整后，必然会影响其父节点需要二次调整。但是从下往上的方式不需要考虑父节点，因为当前节点调整完之后，当前节点必然比它的所有子节点都大，所以，只会影响到子节点二次调整。相比之下，从下往上的遍历方式比从上往下的方式少了父节点的二次调整。

那么，该如何知道最后一个非叶子节点的位置，也就是索引值？

对于一个完全二叉树，在填满的情况下（非叶子节点都有两个子节点），每一层的元素个数是上一层的二倍，根节点数量是1，所以最后一层的节点数量，一定是之前所有层节点总数+1，所以，我们能找到最后一层的第一个节点的索引，即节点总数/2（根节点索引为0），这也就是第一个叶子节点，所以第一个非叶子节点的索引就是第一个叶子结点的索引-1。那么对于填不满的二叉树呢？这个计算方式仍然适用，当我们从上往下，从左往右填充二叉树的过程中，第一个叶子节点，一定是序列长度/2，所以第一个非叶子节点的索引就是arr.length / 2 -1。

现在找到了最后一个非叶子节点，即元素值为2的节点，比较它的左右节点的值，是否比他大，如果大就换位置。这里因为1<2，所以，不需要任何操作，继续比较下一个，即元素值为8的节点，它的左节点值为9比它本身大，所以需要交换

 

交换后的序列为：

4 5 9 2 3 8 7 1

 

因为元素8没有子节点，所以继续比较下一个非叶子节点，元素值为5的节点，它的两个子节点值都比本身小，不需要调整；然后是元素值为4的节点，也就是根节点，因为9>4，所以需要调整位置

交换后的序列为：

95423871                

此时，原来元素值为9的节点值变成4了，而且它本身有两个子节点，所以，这时需要再次调整该节点

交换后的序列为：

95823471                

到此，大顶堆就构建完毕了。满足大顶堆的性质。

2、排序序列，将堆顶的元素值和尾部的元素交换

交换后的序列为：

15823479                

然后将剩余的元素重新构建大顶堆，其实就是调整根节点以及其调整后影响的子节点，因为其他节点之前已经满足大顶堆性质。

交换后的序列为：

85723419                

然后，继续交换，堆顶节点元素值为8与当前尾部节点元素值为1的进行交换

交换后的序列为：

15723489                

重新构建大顶堆

交换后的序列为：

75423189                

继续交换

交换后的序列为：

15423789                

继续交换

交换后的序列为：

13425789                

重新构建大顶堆

构建后的序列为：

43125789                

继续交换

交换后的序列为：

23145789                

重新构建大顶堆

构建后的序列为：

32145789                

继续交换

交换后的序列为：

12345789                

重新构建大顶堆

构建后的序列为：

21345789                

继续交换

交换后的序列为：

12345789                

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int len=nums.size();
        buildMaxheap(nums, len);            //先将初始数组构建大顶堆
        for(int i=len-1;i>0;i--){           
            swap(nums,0,i);                 //交换大顶堆堆头和堆尾
            len--;
            heapfy(nums, 0, len);           //交换后的堆继续大顶堆化
        }
        return  nums;
    }
    void buildMaxheap(vector<int>&nums,int len){
        for(int i=len/2-1;i>=0;i--){
            heapfy(nums,i,len);             //对每个结点进行左右孩子判断
        }
    }
    void heapfy(vector<int>&nums,int i,int len){
        int left=2*i+1;
        int right=2*i+2;
        int largest=i;
        if(left<len&&nums[left]>nums[largest]){     //判断左右孩子是否存在以及是否复合大顶堆，不符合就换
            largest=left;
        }
         if(right<len&&nums[right]>nums[largest]){
            largest=right;
        }
        if(largest!=i){
            swap(nums,largest,i);       //进行交换
            heapfy(nums, largest, len); //换完之后是不是可能换了之后的叶子结点不符合大顶堆？所以继续递归大顶堆
        }
    }
    void swap(vector<int>&nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
};

6.归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

1. 算法思想

   该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

   动态效果示意图：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

若将两个有序表合并成一个有序表，称为二路归并。

归并排序核心步骤：

1. 递归法

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int len=nums.size();
        vector<int>a;
        for(int i=0;i<len;i++){
            a.push_back(0);
        }
        int left=0;
        int right=len-1;
        Mergesort(a, left,  right, nums);
        return nums;
    }
    void Mergesort(vector<int>&a,int left,int right,vector<int>&nums){
        if(left>=right){
            return ;
        }
        int mid=(left+right)/2;
        Mergesort(a, left,mid,nums);                //进行递归，将数组分为两个两个
        Mergesort(a, mid+1, right, nums);
        int begin1=left,end1=mid;                //对上一步已经排好序组合好的进行排序
        int begin2=mid+1,end2=right;
        int i=left;
        while(begin1<=end1&&begin2<=end2){
            if(nums[begin1]<nums[begin2]){
                a[i++]=nums[begin1++];
            }
            else{
                a[i++]=nums[begin2++];
            }
        }
        while(begin1<=end1){
            a[i++]=nums[begin1++];
        }
        while(begin2<=end2){
            a[i++]=nums[begin2++];
        }
        for(int j=left;j<=right;j++){
            nums[j]=a[j];                           //将此次组合好的放到原数组中
        }   
    }
};

2. 迭代法

非递归实现的思想与递归实现的思想是类似的。

不同的是，这里的序列划分过程和递归是相反的，不是一次一分为二，而是先1个元素一组，再2个元素一组，4个元素一组....直到将所有的元素归并完。

静态图示：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int len=nums.size();
        vector<int>a;
        for(int i=0;i<len;i++){
            a.push_back(0);
        }
        int gap=1;
        while(gap<len){
            int index=0;
            for(int i=0;i<len;i+=gap*2){
                int begin1=i,end1=i+gap-1;
                int begin2=i+gap,end2=i+2*gap-1;
                //当数组元素个数不满足2^n时，当gap取到最大时总会有两组元素不匹配的情况
                if(end1>=len||begin2>=len){
                    break;                      //如果只有一个数组
                }
                if(end2>=len){
                    end2=len-1;                //有第二个数组时及时调整边界
                }
                while(begin1<=end1&&begin2<=end2){
                    if(nums[begin1]<nums[begin2])a[index++]=nums[begin1++];
                    else a[index++]=nums[begin2++];
                }
                while(begin1<=end1)a[index++]=nums[begin1++];
                while(begin2<=end2)a[index++]=nums[begin2++];
                for(int j=0;j<index;j++){
                    nums[j]=a[j];
                }
            }
            gap*=2;
        }
        return nums;
    }
};

7.快速排序*

这里是排序算法的重点了，非常重要！

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，

其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

1. hoare版本

   具体思路是：

   1. 选定一个基准值，最好选定最左边或者最右边，选中间会给自己找麻烦。

   2. 确定两个指针left 和right 分别从左边和右边向中间遍历数组。

   3. 如果选最右边为基准值，那么left指针先走，如果遇到大于基准值的数就停下来。

   4. 然后右边的指针再走，遇到小于基准值的数就停下来。

   5. 交换left和right指针对应位置的值。

   6. 重复以上步骤，直到left = right ，最后将基准值与left(right)位置的值交换。

这样基准值左边的所有数都比他小，而他右边的数都比他大，从而他所在的位置就是排序后的正确位置。

之后再递归排以基准值为界限的左右两个区间中的数，当区间中没有元素时，排序完成。

动图演示：

这里选定基准值为最右边的元素。

单趟图解：

继续按照上述步骤进行。。。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int len=nums.size();
        int left=0,right=len-1;
        quicksort(nums, left, right);
        return nums;
    }
    void quicksort(vector<int>&nums,int left,int right){
        if(left>=right){
            return;
        }
        int key=quicksortpart(nums, left, right);       //key左边都小，key右边都大
        quicksort(nums, left, key-1);
        quicksort(nums, key+1,right);
    }
    int quicksortpart(vector<int>&nums,int left,int right){
        int key=right;
        while(left<right){
            while(left<right&&nums[left]<=nums[key]){
                left++;
            }
            while(left<right&&nums[right]>=nums[key]){
                right--;
            }
            swap(nums[right],nums[left]);
        }
        swap(nums[left],nums[key]);
        return left;
    }
};

2. 挖坑法

   挖坑法与上面的方法类似。

   具体思路是：

   1. 先将选定的基准值(最左边)直接取出，然后留下一个坑，

   2. 当右指针遇到小于基准值的数时，直接将该值放入坑中，而右指针指向的位置形成新的坑位，

   3. 然后左指针遇到大于基准值的数时，将该值放入坑中，左指针指向的位置形成坑位，

   4. 重复该步骤，直到左右指针相等。最后将基准值放入坑位之中。

      之后也是以基准值为界限，递归排序基准值左右区间。

动图演示：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int len=nums.size();
        int left=0,right=len-1;
        quicksort(nums, left, right);
        return nums;
    }
    void quicksort(vector<int>&nums,int left,int right){
        if(left>=right){
            return;
        }
        int key=quicksortpart(nums, left, right);       //key左边都小，key右边都大
        quicksort(nums, left, key-1);
        quicksort(nums, key+1,right);
    }
    int quicksortpart(vector<int>&nums,int left,int right){
        int key=nums[left],hole=left;                       //不是交换我挖坑
        while(left<right){
            while(left<right&&nums[right]>=key){
                right--;
            }
            nums[hole]=nums[right];
            hole=right;
               while(left<right&&nums[left]<=key){
                left++;
            }
            nums[hole]=nums[left];
            hole=left;
        }
        nums[hole]=key;
        return hole;
    }
};

3. 前后指针法

前后指针法是一个新思路，不太好理解，但是代码比较简单。

具体思路是：

1. 选定基准值，定义prev和cur指针(cur = prev + 1)

2. cur先走，遇到小于基准值的数停下，然后将prev向后移动一个位置

3. 将prev对应值与cur对应值交换

4. 重复上面的步骤，直到cur走出数组范围

5. 最后将基准值与prev对应位置交换

6. 递归排序以基准值为界限的左右区间

动图演示：

单趟演示：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int len=nums.size();
        int left=0,right=len-1;
        quicksort(nums, left, right);
        return nums;
    }
    void quicksort(vector<int>&nums,int left,int right){
        if(left>=right){
            return;
        }
        int key=quicksortpart(nums, left, right);       //key左边都小，key右边都大
        quicksort(nums, left, key-1);
        quicksort(nums, key+1,right);
    }
    int quicksortpart(vector<int>&nums,int left,int right){
        int pre=left,cur=left+1,key=left;
        while(cur<=right){
            if(nums[cur]<nums[key]){
                ++pre;
                swap(nums[cur],nums[pre]);
            }
            cur++;
        }
        swap(nums[key],nums[pre]);
        return pre;
    }
};

4. 快速排序优化

上面就是快速排序递归的三种方法。

但是上面的程序还有一些缺陷：

在基准值的选择上，如果选择的基准值为恰好为最小值，会进行不必要的递归。

在排序大量有序数据或者接近有序数据时，效率会比较低，甚至可能会出现程序崩溃的情况。

这是因为在排序有序数据时，快速排序的递归调用次数过多，会导致栈溢出的情况。

为了解决这些问题，这里有两种优化方法：

1. 三数取中法选基准值

2. 递归到小的子区间时，可以考虑使用插入排序

1.即在在起始位置，中间位置，末尾位置中选出中间值，作为基准值。

//三数取中
 
int MidIndex(int* a, int left, int right)
{
    int mid = (left + right) / 2;
    //防止mid越界
    //int mid = left+(right - left) / 2;
 
    if (a[left] < a[right])
    {
        if (a[mid] < a[left])
        {
            return left;
        }
        else if (a[mid] > a[right])
        {
            return right;
        }
        else
        {
            return mid;
        }
    }
    else
    {
        if (a[mid] > a[left])
        {
            return left;
        }
        else if (a[mid] < a[right])
        {
            return right;
        }
        else
        {
            return mid;
        }
    }
}

 2.类似于二叉树，每个子树都会进行一次递归调用，越到下面递归调用会越多。为了减少递归调用，当到递归到下层时，我们可以使用其他的排序来替代。这里我们使用插入排序

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int len=nums.size();
        int left=0,right=len-1;
        quicksort(nums, left, right);
        return nums;
    }
    void quicksort(vector<int>&nums,int left,int right){
        if(left>=right){
            return;
        }
        if(right-left<10)Intersortsort(nums,left,right);
        int key=quicksortpart(nums, left, right);       //key左边都小，key右边都大
        quicksort(nums, left, key-1);
        quicksort(nums, key+1,right);
    }
    int quicksortpart(vector<int>&nums,int left,int right){
        int mid=MidIndex(nums, left,  right);
        swap(nums[mid],nums[left]);
        int pre=left,cur=left+1,key=left;
        while(cur<=right){
            if(nums[cur]<nums[key]){
                ++pre;
                swap(nums[cur],nums[pre]);
            }
            cur++;
        }
        swap(nums[key],nums[pre]);
        return pre;
    }
    //三数取中
    int MidIndex(vector<int> a, int left, int right)
    {
        int mid = (left + right) / 2;
        //防止mid越界
        //int mid = left+(right - left) / 2;
    
        if (a[left] < a[right])
        {
            if (a[mid] < a[left])
            {
                return left;
            }
            else if (a[mid] > a[right])
            {
                return right;
            }
            else
            {
                return mid;
            }
        }
        else
        {
            if (a[mid] > a[left])
            {
                return left;
            }
            else if (a[mid] < a[right])
            {
                return right;
            }
            else
            {
                return mid;
            }
        }
    }
    vector<int> Intersortsort(vector<int>& nums,int left,int right) {
       for(int i=left;i<right;i++){
           int end=i;
           int x=nums[end+1];
           while(end>=0){
               if(nums[end]>x){
                   nums[end+1]=nums[end];
                   end--;
               }
               else break;//前面都是已经排好顺序的元素一个小个个小
           }
           nums[end+1]=x;
       }
       return nums;
    }
};

8. 计数排序

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤 1. 统计相同元素出现次数 2. 根据统计的结果将序列回收到原来的序列中

动图演示：

注意：计数排序在排负数时，可将负数的类型转化成 unsigned int。

数组中元素有正有负的情况时不适用计数排序。

计数排序的特性总结：

计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。 时间复杂度：O(MAX(N,范围)) 空间复杂度：O(范围)稳定性：稳定

// 计数排序
void CountSort(int* a, int n)
{
    assert(a);
    // 创建计数数组，数组大小为原数组中最大值-最小值+1
    int max = a[0], min = a[0];
    int i = 0;
    for (i = 0; i < n; i++)
    {
        if (a[i] > max)
        {
            max = a[i];
        }
        if (a[i] < min)
        {
            min = a[i];
        }
    }
    int range = max - min + 1;
    int* count = (int*)malloc(sizeof(int) * range);
    // 初始化计数数组为0
    memset(count, 0, range * 4);
 
    // 统计次数
    for (i = 0; i < n; i++)
    {
        count[a[i] - min]++;
    }
    // 根据次数，进行排序
    int j = 0;
    for (i = 0; i < range; i++)
    {
        while (count[i]--)
        {
            a[j++] = i+min;
        }
    }
    free(count);
    count = NULL;
}

 

9.八大排序总结