常见排序算法(一)

2019-05-04 09:39:42来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

排序:

  1、排序在计算机数据处理中经常遇到,在日常的数据处理中,一般可以认为有 1/4 的时间用在排序上,而对于程序安装,

     多达 50% 的时间花费在对表的排序上。简而言之,排序是将一组杂乱无章的数据按一定的规律顺次排列起来

  2、内排与外排:根据排序方法在排序过程中数据元素是否完全在内存而划分,若一部分数据在外存,则为外排,否则,为内排

  3、排序算法的稳定性:根据排序后相同元素顺序是否会发生改变而定,

     如两个数 a 与 b,a == b 且 a 在 b 的前面,若排序后 a 仍然在 b 的前面,则为稳定的,否则,为不稳定的

  4、排序算法的性能评估:算法的执行时间是衡量算法好坏的最重要参数,其时间开销可用算法执行中的数据比较次数移动次数来衡量

 

排序算法:

  1、时间复杂度:

    a、平方阶 (O(n2)) 排序 各类简单排序:直接插入、直接选择和冒泡排序

    b、线性对数阶 (O(nlog2n)) 排序:快速排序、堆排序和归并排序

    c、O(n1+§)) 排序,§ 是介于 0 和 1 之间的常数:希尔排序

    d、线性阶 (O(n)) 排序:基数排序,桶排序和计数排序

 

  2、稳定性:

    a、稳定的排序算法:冒泡排序、插入排序、归并排序、计数排序、桶排序和基数排序

    b、不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序

注:稳定性是相对的,例如我们把比较冒泡排序里对两个元素比较的算法改成大于等于,它会变成不稳定的!

 

  3、比较与非比较:

    a、比较排序:冒泡排序、插入排序、希尔排序、选择排序、快速排序、归并排序和堆排序

    b、非比较排序:计数排序、桶排序和基数排序

 

 

十大经典排序算法:

以下均按非降序排序

  1、冒泡排序(bubbleSort):

    a、比较相邻两个元素,若前者的大于后者,则交换这两个元素

    b、向后移动一项,再执行比较交换操作;当移动到最后一位时,这个元素即为本轮最大值

    c、从新从头开始,除了最后一项,执行 a、b 操作,直到排序完成

注:在排序过程中,我们可以设置一个标志判断在一轮排序中是否有交换元素,若一轮排序过后仍无交换,则说明排序已完成

#include <iostream>
#include <vector>
#include <cstdlib>

//采用引用的方式传参,否则传入的只是一个不会改变原数据的形参 
void bubbleSort(std::vector<int>& nums);

int main()
{
    std::vector<int> nums;
    int len = 0;
    std::cout<<"请输入长度:";
    do {
        std::cin>>len;
        if (len <= 0)
//            标准错误流,输出错误信息 
            std::cerr<<"请输入正整数:";
    } while (len <= 0);
    int num = 0;
    std::cout<<"输入 "<<len<<" 个数: ";
//    size_t 是 unsigned_int 类型,建议在使用下标时使用,但若将负数赋值给它,则会将该数转换为正数,从而产生错误 
    for (size_t i = 0; i < len; ++i) {
        std::cin>>num;
        nums.push_back(num);
    }
    
    bubbleSort(nums);
    std::cout<<"排序后的数组:";
//    自由 for 循环 
    for (int num : nums)
//        std::ends 输出空白符,不同电脑的空白符可能不一样 
        std::cout<<num<<std::ends;
    std::cout<<std::endl;
    
    system("pause");
    
    return 0;
}

void bubbleSort(std::vector<int>& nums)
{
//    设置交换标志,若一次循环后所有元素都未发生交换,则说明数组已经排列好,可提前退出 
    bool exchange = false;
    size_t len = nums.size();
    for (size_t i = 1; i < len; ++i) {
        exchange = false;
//        为了方便,我把最小的元素移动到了最前 
        for (size_t j = len-1; j >= i; j--) {
            if (nums[j-1] > nums[j]) {
                int temp = nums[j-1];
                nums[j-1] = nums[j];
                nums[j] = temp;
                exchange = true;
            }
        }
        if (!exchange)
            return;
    }
}
View Code

 

   2、选择排序(selectionSort):

    a、在初始序列 R[i...n-1] 中找到最小的元素,放到 R[i] 处,i=0,n=待排对象大小

    b、++i

    c、重复执行 a、b 操作,直至第 n-1 轮

void selectionSort(std::vector<int>& nums)
{
    size_t len = nums.size();
//    在每次循环里选出最小的一个排在前面 
    for (size_t i = 0; i < len-1; ++i){
        int min = i;
        for (size_t j = i+1; j < len; ++j){
            if (nums[j] < nums[min])
                min = j;
        }
        if (i != min){
            int temp = nums[i];
            nums[i] = nums[min];
            nums[min] = temp;
        } 
    }
    return ;
}
View Code

 

  3、简单插入排序(insertionSort)

    a、从第一个元素开始,该元素可以认为已经被排序

    b、取出下一个元素,在已经排序的元素序列中从后向前扫描

    c、如果该元素大于新元素,将该元素移到下一位置

    d、重复操作 c,直到找到已排序的元素小于或等于新元素的位置

    e、将新元素插入到该位置后

    f、重复操作 b-e

void insertionSort(std::vector<int>& nums)
{
    size_t len = nums.size();
    
    for (size_t i = 1; i < len; i++) {
        int temp = nums[i];
        
//        在循环中把较大的数往后移一位 
        size_t j = i;
        while (j > 0 && temp < nums[j-1]) {
            nums[j] = nums[j-1];
            j--;
        }
        if (j != i)
            nums[j] = temp;
    }
    return ;
}
View Code

 

  4、希尔排序(shellSort):

    a、设对象有 n 个元素,先取整数 gap < n 作为间隔,并将全部元素分为 gap 个子序列,所有距离为 gap 的元素放在同一子序列中,

       在每个子序列中分别施行直接插入排序

    b、缩小间隔 gap,如 gap = gap/3 + 1

    c、重复 a、b 操作,直到取 gap == 1

注:gap 有多种取法,但如果 gap = n/2 或 gap = gap/2 时,只有到最后一步奇数位置才会和偶数位置的数进行比较

void shellSort(std::vector<int>& nums)
{
    int gap = 1, len = nums.size();
//    先让间隔 gap 尽量大 
    while (gap < len)
        gap = gap*3+1;
        
    while (gap > 0){
        for (int i = gap; i < len; i++){
            int temp = nums[i];
            int j = i - gap;
//                     直接插入排序
            while (j >= 0 && nums[j] > temp){
                nums[j+gap] = nums[j];
                j -= gap;
            }
            nums[j+gap] = temp;
        }
        gap /= 3;
    }
    return ;
}
View Code

 

  5、快速排序(quickSort):

    a、从数列中挑出一个元素,称为 “基准”(一般为第一个元素)

    b、重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。

       在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作

    c、递归地把小于基准值元素的子数列和大于基准值元素的子数列排序

注:快排的非递归算法可以使用栈来实现

 

void quickSort(int* arr, int low, int high)
{
    int star = low, end = high;
    if (star > end)
        return ;
    int temp = arr[star];
    while (star != end) {
//        从后找出小于“基准”的数 
        while (arr[end] >= temp && star < end)
            end--;
//        从前找出大于“基准”的数 
        while (arr[star] <= temp && star < end)
            star++;
//        若还在范围内,则交换这两者 
        if (star < end) {
            int t = arr[star];
            arr[star] = arr[end];
            arr[end] = arr[star];
        }
    }
//    把“基准”移动到“中间” 
    int t = arr[low];
    arr[low] = arr[star];
    arr[star] = t;
    
//    递归 
    quickSort(arr, low, star-1);
    quickSort(arr, star+1, high);
      
        return ;
} 
View Code

 


原文链接:https://www.cnblogs.com/lemonyam/p/10801483.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:模拟(入门)

下一篇:C++ Primer 回炉重铸(一)