我的算法之路 -- Sort排序

Created by miccall (转载请注明出处)
  • 按理说这类文章首先应该讲一些鸡汤啊 鼓励学习什么的话       但是没有

  • 按理说这类文章应该有一些推荐路径或者学习方法       但是没有

  • 按理说这个文章应该和其他的类似 讲些算法之坑       但是没有

  • 那这篇文章出现的意义是什么 没什么 就是我的学习之路      你爱看就看看

排序的前奏

  • [ 只看算法部分的话 这段可以跳过 ]
  •       为了方便和测试数据的大量化 随机化 自动化 。我打算写一个帮助类来完成这个事,但是后来看到一个大牛写的方法,我决定还是套用他的代码。但是秉着学习的态度 我也来一遍抄 一边学 。

        //代码架构 cpp
        #include <iostream>
        #include <ctime>
        #include <cassert>
        #include <cstdlib>
        using namespace std;

        namespace SortTestHelper{

            //生成n个元素的随机数组
            int* generateRandomArray(int n,int rangeL ,int rangeR){{
             //code.
            }

            //生成n个元素的近乎有序的数组
             int* generateNearlyOrderedArray(int n,int swapTimes){

            }

            //打印数组
            template<typename T>
             void printArray(T arr[] , int n){

             }

             //是否有序
             template<typename T>
             bool issorted(T arr[] ,int n ){

             }

             //测试算法的时间 性能
             template<typename T>
             void testSort(string sortName ,void(*sort)(T[] , int) , T arr[] , int n ){

             }

             //复制数组
             int* copyIntArray(int a[] , int n){

             }


        }

生成n个元素的随机数组

  • @param :生成包含 n个元素 的随机数组 , 每一个元素的范围是参数指定的 [rangeL , rangeR] 区间 。

  • @思路 :设置随机种子 在用户指定的两个值之间取随机数 让他成为数组的一个元素

  • @技巧 :为了方便 先new一个数组的指针 循环遍历这个数组 ,给每个位置赋值。其值就是我们运算的结果 返回这个指针

  • @局部详解 : rand() % x 表示的是 0到x的随机数,而x表示的是范围的最大值。此时我们指定的值就是前闭后闭范围的( rangeR - rangeL + 1 ) 这样表示的就是0到( rangeR - rangeL + 1 )范围的数。然后我们加上rangeL 相当于一个偏移 就达到我们的要求了。

  • assert的作用是现计算表达式 expression ,如果其值为假(即为0),那么它先向stderr打印一条出错信息,然后通过调用 abort 来终止程序运行


        int* generateRandomArray(int n,int rangeL ,int rangeR){
            assert(rangeL <= rangeR); 
            int *arr = new int[n];
            srand(time(NULL));
            for (int i = 0; i < n; i ++)
            {
                arr[i] = rand() % ( rangeR - rangeL + 1 ) + rangeL ; 
            }
            return arr ;
        }

生成n个元素的近乎有序的数组

  • @param : 生成包含 n个元素 的随机数组 , 但这些数组几乎是有序的 只有有参数swapTimes 个值是随机的 。

  • @思路 :很简单,与上一个类似 这个方法的目的是为了比较不同算法对不同程度排序的优劣性 这个算法只要循环n次 ,逐个加一排列 ,在随机swapTimes的次数 ,对列表里面的数据进行交换位置 这样达到的数组 虽然不是有序的,但是大部分的段落内,是有序的 。

  • @技巧 : swap(x ,y) 函数用于交换x,y的值 。

  • 这样我们就得到了一个近乎有序的数组

        int* generateNearlyOrderedArray(int n,int swapTimes){
            int *arr = new int[n];
            for (int i = 0; i < n; i++ )
                arr[i] = i ;
            srand(time(NULL)); 
            for (int i = 0; i < swapTimes; i++ )
            {
                int posx = rand() % n ;
                int posy = rand() % n ;
                swap(arr[posx] ,arr[posy]);
            }
            return arr ;
        }

打印数组

  • @param : 打印包含 n个元素 的数组 T 。

  • @技巧 : 使用了函数模板 方便不同类型的数据排序


        template<typename T>
        void printArray(T arr[] , int n)
        {
            for (int i = 0; i < n; i++)
            {
                cout<< arr[i] << " " ; 
            }
            cout<<endl;
            return ; 
        }

是否有序

  • @param : 判断包含 n个元素 的数组 T 是否是有序的 。

  • @思路 : 这个实现也非常的简单 遍历一遍数组 看看他是否存在前一位比后一位数值大的数


        template<typename T>
        bool issorted(T arr[] ,int n )
        {
            for (int i = 0; i < n-1; i++ )
            {
                if( arr[i] > arr[ i + 1 ] )
                {
                    cout<<" i : "<<i<<"  arr[i] :"<<arr[i]<<endl;
                    cout<<" i+1 : "<<i+1<<"  arr[i+1] :"<<arr[i+1]<<endl;
                    return false ; 
                }
            }
            return true ; 
        }

测试算法的时间 性能

  • @param : 测试 sortname的排序方法 调用他之后 测试包含 n个元素 的数组 T 求出排序所经历的时间 。测试算法的时间和性能 我们为了以后对比不同的算法 我们指定不同名称的算法 。第二个参数是调用的函数 让用户传入一个执行排序算法的函数 以及数组 长度

  • @思路 : 调用传入的函数 对数组进行排序 然后分别记录开始和结束的时间

  • @详解 : 使用c++ 的clock()函数 他返回一个clock_t 的时钟周期,记录开始和结束的时间 。那就用这两个值来做差求出中间执行的时间 。CLOCKS_PER_SEC c++定义的一个值 每秒执行的时钟周期个数 那么double(endtime - starttime) / CLOCKS_PER_SEC 计算得到的值 ,我们就可以直观的看到时间了。


        template<typename T>
        void testSort(string sortName ,void(*sort)(T[] , int) , T arr[] , int n )
        {
            clock_t starttime = clock();
            sort(arr , n );
            clock_t endtime = clock();

            //测试是否排序成功 
            assert( issorted(arr,n) );
            cout<< sortName << " : " << double(endtime - starttime) / CLOCKS_PER_SEC << " s " << endl;
            return ;   
        }

复制数组

  • @param : 复制一个包含 n个元素 的数组 T 的数组到一个新的空间 并返回其指针
        int* copyIntArray(int a[] , int n)
        {
            int* arr = new int[n];
            copy(a ,a+n, arr);
            return arr ;
        }

使用我们的帮助类

  • 这是一个使用SortTestHelper类的一个模板
        #include <iostream>
        #include "sortTestHelper.h"
        using namespace std; 

        //以后要写的排序算法 
        template<typename T>
        void selectionSort(T arr[], int n ){
            //code ...
        }

        int main()
        {
            //使用我们的帮助类 生成一个n个元素 每个元素区间是0到n 的一个数组 
            int n = 1000;
            int *arr = SortTestHelper::generateRandomArray(n,0,n);

            //使用我们的帮助类  测试算法的性能 
            SortTestHelper::testSort("Seletion Sort" , selectionSort , arr , n );

            //删除新开的空间 
            delete[] arr ; 
            return 0 ;
        }

排序算法之路的第一步

  • O(N^2) 的排序算法

冒泡 BubbleSort

  • 给定一个数组,从第一元素个开始,比较相邻的元素。如果第一个比第二个大,就交换他们两个。

  • 比较完第一个和第二个 ,然后比较第二个和第三个 ,然后是第三个和第四个 。

  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,持续结束后 ,最后的元素应该会是最大的数。

  • 针对所有的元素重复以上的步骤,除了最后一个。

  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。


        template<typename T>
        void BubbleSort(T arr[], int n ){    
            for (int j = 0; j < n; j++)
            {
                 for (int i = 0; i < n; i++)
                 {
                     //如果后一项比当前项小 则交换他们  
                     if( arr[i+1] < arr[i] )
                    {
                        //交换arr[i+1] 和 arr[i] 
                        swap(arr[i+1] , arr[i]);
                    }
                 }    
            }
        }

选择 SelectionSort

  • 首先在整个数组里面 找出大小是第一名的位置

  • 让这个数与当前数组最前位置 交换

  • 这样 最小的数就出现在了数组的最前面 此时这个就不参与以后的交换了 从下一个开始

  • 之后 在剩下的部分重复寻找和交换操作 每次找到剩下的中最小的 与之前未排好序的部分的第一个做交换

  • 这样n次以后 所有的部分就都排好了

        template<typename T>
        void selectionSort(T arr[], int n ){
            for (int i = 0; i < n; i++)
            {
                //寻找 [i,n] 区间的最小值 
                int minIndex = i ; // 索引
                for (int j = i + 1 ; j < n; j++)
                {
                    if(arr[j] < arr[minIndex])
                        minIndex = j ;
                }
                //交换位置 
                swap(arr[i],arr[minIndex]);
            }
        }
  • 选择排序法 是对 定位比较交换法(也就是冒泡排序法) 的一种改进。

插入 InsertionSort

  • 首先 数组的第一个元素不动 从第二个开始 如果比第一个大 那么忽略他看下一个 ,如果比第一个小 则放到第一个的前面。然后再看第三个

  • 第三个要与前面的逐个比较 看看他是排第一 还是第二 还是不动 。

  • 其余的都是这样 ,不断地与前面所有的数做比较 把他插入到自己该插入的地方

  • 每次都排好一个数 这样遍历一次数组 ,所有的数就都可以排好了

        template<typename T>
        void insertionSort(T arr[], int n ){
            //0的位置看作已经排序好的 
            for (int i = 1; i < n; i++ )
            {
                //取出的e :寻找arr[i] 合适的插入位置 
                T e = arr[i];
                int j ; 
                for ( j = i ; j > 0 && arr[ j - 1] > e ; j-- )
                {
                    //swap( a rr[ j ] , arr[ j-1 ]); 
                    arr[ j ] = arr[ j-1 ];
                }
                arr[ j ] = e ;
            }
        }
  • 在近乎有序的数组来说 插入排序的性能要远远优于选择排序

  • 在全部有序的数组 插入排序的时间复杂度会上升为O(n)

排序算法之路的第二步

  • O(nlogn) 的排序
  • 当数据量很小时 n方的算法和nlogn的算法相差只有一个数量级 在现代的计算机相差只有几毫秒 根本感觉不到
  • 当随着数据量的提高 nlogn的算法的优势会越来越大 在十的五次方逐个数据量时,虽然也不是很大,此时nlogn的算法会比n方快六千倍,什么感念。nlogn处理一天的东西,n方要处理十五年。

归并 MergeSort

  • @思路 :把一个数组分成两半 ,左边和右边的数组分别排序 ,最后归并到一起 。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

  • 递归的思路,当对左右的数组分别进行排列的时候 在把他们拆分成更小的数组 。分别排序和归并。

  • 当对最后分到只有一个元素时,他们本身就是有序的,所以我们只进行归并就可以了

  • 不断归并到上一个层级,直到归并到最高层级,这样就可以排好序了 。

  • 层级最多有多少层呢 大概想一下 不断地二分 二分,最后剩下一个元素,那就是log以二为底。长度的对数的层级
    8个元素的数组,就可以分为三个层级。就这样 。

  • 归并的过程依然值得考虑 我们可以使用递归的方法,但是在原有数组的基础上对他递归,任然很难,所以我们得另开一个数组,来辅助我们的归并过程 。我们牺牲了空间复杂度来换取时间复杂度。

  • @算法解析:
  • 算法一共有三个方法
  • void __merge( T arr[] , int l , int mid , int r )
  • void __mergeSort(T arr[] , int l , int r)
  • void mergeSort(T arr[], int n )

  • 第三个是主入口 用来归并排序长度为n的数组T。

  • 那么算法我们调用的就是第二个方法 l和r分别表示数组的开始和结尾的索引
  • 因为我们要递归 就要不断地更改开始和结尾的索引 。
  • 在第二个方法里面 ,我们数组进行了递归二分 和调用第一个方法 。

  • 第一个方法 他要一个额外的辅助数组 。将二分好的arr[l….mid] 和 arr[mid+1 …… r] 两部分进行归并操作

  • 归并方法就是 每次在两个小数组里面找最小的 将他放到一个新的数组里面 。如果是从第一个里面取的,就让他的下标++。如果是第二个中取的 同理让他的下标++。
    这样遍历结束后 新的数组就是两个短数组的排序结果 。

        //将arr[l....mid]  和 arr[mid+1 ...... r] 两部分进行归并 
        template<typename T>
        void __merge( T arr[] , int l , int mid , int r )
        {
            T aux[ r-l+1 ] ; // 一个额外的辅助数组 
            //把arr[l...r] 复制到 aux[0....r-l+1] 
            for (int i = l; i <= r; i++ )
            {
                //下标的偏移量  l 
                aux[i-l] = arr[i];
            }

            //两个位置的索引 
            //i表示前半段搜寻位置  j表示后半段搜寻位置  k则为arr数组的新排序位置
            int i = l  , j = mid + 1 ;

            for (int k = l; k <= r; k++ )
            {
                //处理越界 (当某一段已经提前结束搜寻 只剩下一段 ,直接把这一段复制过来 )
                if( i > mid ) 
                {
                    arr[k] = aux[j-l];
                    j++;
                }else if ( j > r )
                {
                    arr[k] = aux[i-l];
                    i++;
                } // 正常搜寻步骤 谁小取谁放到arr[k]的位置 然后位置偏移 
                else if( aux[i-l] < aux[j-l] )
                {
                    arr[k] = aux[i-l];
                    i++;
                }
                else{
                    arr[k] = aux[j-l];
                    j++;
                }
            }
        }

        //递归使用的归并排序 对arr[l.....r]的范围进行排序 
        template<typename T>
        void __mergeSort(T arr[] , int l , int r){
            if( l >= r )  //数据集为空  可能只有一个元素 
             return ;

            // arr中间位置 
            int mid = ( l + r ) / 2 ; 

            //递归的二分 
            __mergeSort(arr , l , mid );
            __mergeSort(arr , mid+1 , r);
            //排序 
            __merge(arr, l , mid ,r );
        }

        template<typename T>
        void mergeSort(T arr[], int n ){
            //n个长度的数组 下标是0到n-1 
            __mergeSort( arr ,0,n-1);
        }

向上归并 mergeSortBU

  • 向上归并的算法是在归并的基础上 ,优化了不分开数组,而是直接对数据进行向上归并。
        template<typename T>
        void __merge(T arr[],int l ,int mid ,int r)
        {
            T aux[ r-l+1 ] ;
            for (int i = l; i <= r; i++ )
            {
                aux[i-l] = arr[i];
            }
            //两个位置的索引 
            int i = l  , j = mid + 1 ;
            for (int k = l; k <= r; k++ )
            {
                if(i > mid ) 
                {
                    arr[k] = aux[j-l];
                    j++;
                }else if ( j > r )
                {
                    arr[k] = aux[i-l];
                    i++;
                }
                else if( aux[i-l] < aux[j-l] )
                {
                    arr[k] = aux[i-l];
                    i++;
                }
                else{
                    arr[k] = aux[j-l];
                    j++;
                }
            }
        }
        //自底向上的归并排序 
        template<typename T>
        void mergeSortBU(T arr[], int n ){    

            for (int sz = 1; sz < n; sz+=sz )
            {
                for(int i = 0   ; i+sz < n  ; i += sz +sz )
                    //对 arr[i...i+sz-1] 和 arr[i+sz .... i+2*sz - 1 ] 归并排序 
                    __merge(arr , i ,  i+sz-1 , min(i+sz+sz-1 , n-1 ) );
            }

        }

快速 QuickSort

  • @思路:快速排序也可以看成是一种二分排序,我们找到一个基准后 让前半部分都比这个基准小 后半部分都比基准大 ,这样我们分别对前后两部分进行排序 就不用进行归并的操作 依然满足整体的有序性 。

  • @难点:如何去找这个基准 如何让前后两部分各自有序 递归的实现 。

  • @详解:
    1 从数列中挑出一个元素,称为 “基准”(pivot)一般的都选数组的第一个数 。
    2 从第二个开始遍历数组,发现一个元素比基准值小的 ,就摆放在基准前面 ,法线一个元素比基准值大的,就摆在基准的后面(相同的数可以到任一边)。在这个遍历结束之后,该基准 就替换到处于数列的中间位置。这个过程叫 分区(partition)操作。
    3 递归的(recursive)把 小于 基准值元素的子数列 和 大于基准值元素的子数列 进行第一步操作。

  • @优化:在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种在我们优化之后,出现的概率就非常非常低了。

  • 因为快速排序的不稳定性 我们可以优化 当长度小于15时 ,可以使用插入排序

  • @优势:快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来

  • quick

  • 递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。



        //对arr[l...r] 的部分 partition 操作 
        //返回 p 使得 arr[l   ... p-1] < arr[p]   
        //            arr[p+1 ...   r] > arr[p]  


        template<typename T>
        int __partition( T arr[] , int l ,int r )
        {
            //第二次优化 : 指定一个标准  
            swap (arr[l] , arr[rand() % (r-l+1) + l ] ); 
            T v = arr[l];

            //第一位是标定 排序从下一位开始 
            //arr[ l+1 ... j ] <  v     &&    arr[ j+1 ... i ) > v 

            int j = l ;  

            //遍历数组 
            for ( int i = l+1 ; i <= r; i++ )
            {
                if( arr[i] < v ){

                    //如果 找到一个比v小的数 就和第一个排序数交换 
                    swap(arr [ ++j ] , arr[ i ] ) ;
                    //j++ ;
                }  
            }


            //循环结束后 所有比v小的数在前面 大的数在后面 然后把v放在他们中间 
            swap(arr[l] , arr[j]) ;


            //返回标定量的位置 
            return j ;
        }

        //对arr[l...r] 的部分快速排序  
        template<typename T>
        void __quickSort(T arr[] , int l ,int r )
        {
            //递归处理 
            // if( l >= r ) return ;
            //第一次优化 :         
            if(r - l <= 15 )
            {   
                // 当长度小于15时 ,可以使用插入排序 
                SortTestHelper::insertionSort(arr , r-l);
                return ;
            }


            //标定量  索引值 
            int p = __partition(arr , l , r ) ;


            //递归的对 小于标定量的部分快速排序 
            __quickSort(arr ,  l  , p-1  );

            //递归的对 大于标定量的部分快速排序 
            __quickSort(arr , p+1 ,  r   );

        }


        //排序入口 
        template<typename T>
        void QuickSort(T arr[], int n ){

            //对 数组的 0 到 n-1 进行排序 
            __quickSort(arr,0,n-1);
        }

三路快速 QuickSort3Ways


        /*三路快速排序 对arr[l...r] 的部分快速排序  
        * 将arr[l...r]分为 < v   ==v    >v  三部分 
        * 之后对 <v    >v 两部分继续进行三路快速排序 
        */

        template<typename T>
        void __QuickSort3Ways(T arr[] , int l ,int r )
        {
            //递归处理 
             // if( l >= r ) return ;
            if( r - l <= 15 )
            {   //当长度小于15时 ,可以使用插入排序 
                SortTestHelper::insertionSort(arr , r-l);
                return ;
            }

            //----------------标定量  索引值 
            swap(arr[l] , arr[rand()%(r-l+1)+l]);
            T v = arr[l];
            int lt = l ; // arr[l+1 .... lt] < v 
            int gt = r+1 ; // arr[ gt....t] > v 
            int i = l+1 ; // arr[lt+1 ....i ] == v 
            while( i < gt )
            {
                if( arr[i] < v ){
                    swap(arr[i] , arr[lt+1]);
                    lt++ ; i++ ;
                }
                else if(arr[i]>v){
                    swap(arr[i],arr[gt-1]);
                    gt-- ; 
                }else{
                    //arr[i] == v 
                    i++ ;
                }
            } 
            swap(arr[l] , arr[lt]);

            //---------------------------------------
            __QuickSort3Ways(arr ,  l  , lt-1  );
            __QuickSort3Ways(arr , gt ,  r   );

        }

        template<typename T>
        void QuickSort3Ways(T arr[], int n ){
            srand(time(NULL));
            __QuickSort3Ways(arr,0 ,n-1);
        }

堆排序 Heap

  • 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

  • 堆排序的平均时间复杂度为Ο(nlogn) 。

  • 1.创建一个堆H[0..n-1]
  • 2.把堆首(最大值)和堆尾互换
  • 3.把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
  • 4.重复步骤2,直到堆的尺寸为1