十大基础排序算法

排序算法分类

排序:将一组对象按照某种逻辑顺序重新排列的过程。

  • 按照待排序数据的规模分为:

    1. 内部排序:数据量不大,全部存在内存中;
    2. 外部排序:数据量很大,无法一次性全部存在内存中,因此排序中需要访问外存。
  • 按照排序是否稳定分为:

    1. 稳定排序:相等的元素在排序前后的相对位置不变。例如,a等于b,且原序列a在b前,排序后a仍在b前,则为稳定排序。
    2. 不稳定排序:相等元素在排序前后的相对位置可能发生变化。
  • 按照是否需要额外内存分为:

    1. 原地排序:在排序过程中不申请多余的存储空间,只利用原来存储待排数据的存储空间进行比较和交换的数据排序。
    2. 非原地排序:需要额外内存空间存储数组副本以辅助排序。
  • 按照排序方式分为:

    1. 比较类排序:通过比较来决定元素间的相对次序。
    2. 非比较类排序:不通过元素间的比较进行排序。
      在这里插入图片描述

比较类排序

冒泡排序

冒泡排序是一种典型的交换排序

算法原理:

  • 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  • 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。这一步结束后,排在最后的元素会是所有数据中最大的数;
  • 针对所有的元素重复以上的步骤,除了最后一个;
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

冒泡排序基本代码如下:

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

性能评价:

  • nums[j] == nums[j+1]时,我们并不交换它们。所以冒泡排序是稳定的;
  • 共循环了(n-1)+(n-2)+…+2+1=n(n-1)/2,所以时间复杂度是O(n^2)。

快速排序

快速排序是从冒泡排序演变而来的,实际上是在冒泡排序基础上的递归分治法。
快速排序在每一轮挑选一个基准元素,并让其他比它大的元素移动到数列一边,比它小的元素移动到数列的另一边,从而把数列拆解成了两个部分。

快排也用了分治策略,其本质框架类似二叉树的前序遍历。

其实现代码如下:

void QuickSort(std::vector<int>& nums, int left, int right){
    if(left >= right){
        return;
    }
    //"治"
    int i = left;
    int j = right;
    while(i < j){
        while(i < j && nums[j] > nums[left])     --j;
        while(i < j && nums[i] <= nums[left])    ++i;
        std::swap(nums[i], nums[j]);
    }
    std::swap(nums[i], nums[left]);
    //“分”
    QuickSort(nums, left, i - 1);
    QuickSort(nums, i + 1, right);
}

注意事项

  1. 如果选取数列的第一个元素为基准元素,则从right所指向的元素开始与基准元素进行比较;如果选取数列的最后一个元素为基准元素,则从left所指向的元素开始与基准元素进行比较。
  2. 如果选取数列的第一个元素为基准元素,left所指向的元素与基准元素第一次对比时,left下标与基准元素下标相等(即:判断条件中添加等号);如果选取数列的最后一个元素为基准元素,right所指向的元素与基准元素第一次对比时,right下标与基准元素下标相等。

时间复杂度:O(nlogn)
空间复杂度:O(1)
稳定性:不稳定

插入排序

基本思想:将待排序数据看成由已排序未排序两部分组成。对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

算法流程:

  1. 从第一个元素开始,该元素可以认为已经被排序;
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置后;
  6. 重复步骤2~5。

其实现代码如下:

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

性能评价:

  • 插入排序是稳定的。
  • 时间复杂度为O(n^2)。

希尔排序

在插入排序中,当需要插入的数是较小的数时,后移的次数明显增多,对效率有影响.

希尔排序是对插入排序的优化。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序
在这里插入图片描述

其实现代码如下:

void ShellSort(std::vector<int>& nums){
    const int size = nums.size();
    for(int gap = size / 2; gap > 0; gap /= 2){
        for(int i = gap; i < size; ++i){
            int curr = nums[i];
            int j = i - gap;
            while(j >= 0 && curr < nums[j]){
                nums[j+gap] = nums[j];
                j -= gap;
            }
            nums[j+gap] = curr;
        }
    }
}

选择排序

基本思想:首先在未排序数据找到最小的数,然后把该最小数放到排序序列的末尾,直到所有数据排序完毕。

其实现代码如下:

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

性能评价:

  • 简单选择排序是不稳定排序;
  • 无论什么数据进去,它的比较次数都是n(n-1)/2,所以时间复杂度是O(n^2)。

堆排序

首先将等待排序的数组构造成一个大根堆,构造结束后整个数组当中的最大值就是堆顶元素;
然后将堆顶元素与数组末尾元素交换位置,交换结束后数组末尾元素为最大值,剩下其他的待排序的数组个数为n-1个;
将剩余的n-1个数再次构造成一个大根堆,再将堆顶元素与数组第n-1个位置的元素交换位置,重复上述步骤可以最终得到一个有序数组。

其实现代码如下:

//堆调整
void Heapify(std::vector<int>& nums, int index, int heap_size){
    int parent_index = index;
    int leftChild_index = 2 * parent_index + 1;
    while(leftChild_index < heap_size){
        int maxValue_index = leftChild_index+1 < heap_size && nums[leftChild_index+1] > nums[leftChild_index] ? leftChild_index+1 : leftChild_index;
        maxValue_index = nums[maxValue_index] > nums[parent_index] ? maxValue_index : parent_index;
        if(maxValue_index == parent_index)
            return;
        std::swap(nums[maxValue_index], nums[parent_index]);
        parent_index = maxValue_index;
        leftChild_index = 2 * parent_index + 1;
    } 
}
//堆排序
void HeapSort(std::vector<int>& nums){
    if(nums.size() < 2)
        return;
    int heap_size = nums.size();
    //从下标最大的父节点开始。(最后一个元素的下标是n-1,最后一个父节点的下标是n/2-1)
    for(int i = heap_size/2 - 1; i >= 0; --i)
        Heapify(nums, i, heap_size);

    std::swap(nums[0], nums[--heap_size]);

    while(heap_size > 0){
        Heapify(nums, 0, heap_size);
        std::swap(nums[0], nums[--heap_size]);
    }
}

时间复杂度:O(nlogn)
空间复杂度:O(1)
稳定性:不稳定

归并排序

简单归并排序即二路归并排序。

归并排序采用分治策略,其本质框架类似二叉树的后序遍历,左右子树的递归就是“分”,根结点的处理部分就是“治”。

在这里插入图片描述

其实现代码如下:

std::vector<int> temp;
void MergeSort(std::vector<int>& nums, int left, int right){
    if(left >= right){
        return;
    }
    int mid = left + (right - left) / 2;

    //“分”
    MergeSort(nums, left, mid);
    MergeSort(nums, mid + 1, right);

    //"治"
    int i = left;
    int j = mid + 1;
    int t = left;
    while(i <= mid && j <= right){
        if(nums[i] <= nums[j]){
            temp[t++] = nums[i++];
        }
        else{
            temp[t++] = nums[j++];
        }
    }
    while(i <= mid){
        temp[t++] = nums[i++];
    }
    while(j <= right){
        temp[t++] = nums[j++];
    }
    for(int k = left; k <= right; ++k){
        nums[k] = temp[k];
    }
}

时间复杂度:O(nlogn)
空间复杂度:O(n)
稳定性:稳定

非比较类排序

基数排序

计数排序

桶排序

总结

在这里插入图片描述

不稳定排序记忆口诀:一堆(堆排序)作业,心态不稳,快(快速排序)选择(选择排序)一些(希尔排序)朋友出去玩。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇

)">
下一篇>>