算法之排序算法

排序算法

概念：

• 我们在的排序工作能在主存中完成的，我们就叫这种算法叫做内部排序
• 不能在主存中完成而必须在磁盘或磁带上完成的排序算法叫做外部排序

冒泡排序

概念：

• 冒泡排序是一个很简单的排序算法，冒泡排序是比较相邻的元素，如果第一个比第二个大，就交换他们两个，对每一对相邻元素做同样的工作，执行完毕后，找到第一个最大值，重复以上步骤，每次比较次数-1，直到不需要比较为止。
• 冒泡排序是一种每一轮排序遍历时，抛出当前遍历时的最大值来进行一个到最后升序的排序方法
• 冒泡排序的时间复杂度为O(n²)

注意事项：

• 冒泡排序的时间复杂度不是很好，有时候数据量大就应该考虑其他线性时间复杂度的排序算法

实现代码：

//比较相邻的元素，如果第一个比第二个大，就交换他们两个
//对每一对相邻元素做同样的工作，执行完毕后，找到第一个最大值
//重复以上步骤，每次比较次数-1，直到不需要比较


//冒泡排序,升序排序
void bubbleSort(int an[],int len){
    for(int i=0;i<len-1;i++){
        for(int j=0;j<len-1-i;j++){
            if(an[j]>an[j+1]){
                int temp=an[j+1];
                an[j+1]=an[j];
                an[j]=temp;
            }
        }
    }
}

插入排序

概念：

• 插入排序(insertsort)：插入排序是一个基于比较移动数据来实现有序化的算法，时间复杂度为O(N²)
• 插入排序根据元素的个数N进行N-1趟排序，从第一趟开始，在第P趟，我们将数组索引第P位的元素或者元素位于第P+1位置上的元素与该元素前面的所有元素进行比较，比较后找到该元素存在的对应位置进行移动或者叫做插入(不是交换)
• 第P趟结束，无序的数组或者数据则变成有序化了。

代码：

//插入排序
void insertsort(int *an,int len){
    for(int i=1;i<len;i++){
        int temp=an[i];
        int j;
        for(j=i;j>0&&an[j-1]>temp;j--){
            an[j]=an[j-1];
        }
        an[j]=temp;
    }
}

希尔排序

概念：

• 希尔排序(shellsort)是基于插入排序所优化的算法，该算法依靠增量序列来使到减少相邻元素交换排序的机会以及减少排序执行的趟次，这将比插入排序所花费的时间减少，即使希尔排序的时间复杂度也为O(N²)
• 关于增量序列h，我们将数组的所有元素，按照索引号i,i+h,i+2h…(在数组索引范围0-N-1之内)作为一个序列进行排序，而这个排序是按照序列内的索引号排序因此不会影响到其他索引号的排序，而形成增量序列的h的选取可以自定义，但是希尔建议使用h1=(N-1)/2,h2=h1/2直到hk=1的方式进行形成增量序列(但不是很好)。
• 例如：一个无序数组的元素有12个，则排序该数组需要三趟，h(根据数组最大索引号也就是11除以2取得h1)分别为5，2，1，因此在以5为增量的趟次中，0，5，10为一个序列并将对应号上的元素进行插入排序，1，6，11又为1个序列进行排序。

代码：

• 使用Sedgewick增量作为希尔排序序列的时间复杂度为O(N^7/6)

//希尔排序
void shellsort(int *an,int len){
    for(int i=(len-1)/2;i>0;i/=2){
        //插入排序
        for(int j=i;j<len;j++){
            int temp=an[j],k;
            //根据增量i进行分序列排序
            for(k=j;k>=i&&temp<an[k-i];k-=i){
                an[k]=an[k-i];
            }
            an[k]=temp;
        }
    }
}

//使用Sedgewick增量的希尔排序
void shellsort_pro(int* an,int len){
    /* 初始的增量Sedgewick[Si]不能超过待排序列长度 */
    int Sedgewick[] = {260609,146305,64769,36289,
                       16001,8929,3905,2161,929, 505,
                       209, 109, 41, 19, 5, 1, 0};
    int k;
    for(k=0;Sedgewick[k]>=len;k++);
    for(int d=Sedgewick[k];d>0;d=Sedgewick[++k]){
        for(int i=d;i<len;i++){
            int temp=an[i];
            int j;
            for(j=i;j>=d&&an[j-d]>temp;j-=d){
                an[j]=an[j-d];
            }
            an[j]=temp;
        }
    }
}

堆排序

概念：

• 堆排序(heapsort)：是一个基于二叉堆的排序算法,但是他又跟二叉堆的不一样，二叉堆的数组索引为0的是个哑节点，但是堆排序是得从0开始的
• 堆排序的实现需要根据要实现顺序的方式，将无序的数组在原数组下重新构建成大根堆/小根堆数组，如果要实现升序，就需要构建成大根堆，实现降序，就需要构建成小根堆数组。构建完堆数组，然后以类似堆中操作删除最大元/最小元的方式，将数组实现有序。
• 构建堆(以升序为例)：我们需要拿取数组元素个数N，从(N-1)/2到0遍历(拿取堆中的根节点)，遍历时拿取该根节点的子节点中的最大值，如果最大值大于根节点，就进行根节点与该最大值交换，遍历完毕后就形成了大根堆
• 删除最大/最小元(以升序为例)：要实现升序，则需要拿取数组元素个数N并执行从N-1到1次的删除最大元操作，而最大元就是大根堆数组中的第一位元素，在遍历到索引号为i时，我们需要将最大元与数组索引号为N-i-1的元素进行交换，然后重新构建最大堆保证堆数组的第一位元素就是最大元，跟遍历完毕就得到升序的数组，反之就得到降序的数组。

代码：

#define leftchild(i) (2*(i)+1)    //定义宏函数，找到根节点的左孩子

//构建堆
void buildheap(int* an,int len,int index){
    int temp,child;
    for(temp=an[index];leftchild(index)<len;index=child){
        child=leftchild(index);
        if(child!=len-1&&an[child+1]>an[child]){
            child++;
        }
        if(an[child]>temp){
            an[index]=an[child];
        }else{
            break;
        }
    }
    an[index]=temp;
}

//堆排序
void heapsort(int* an,int len){
    for(int i=(len-1)/2;i>=0;i--){
        buildheap(an,len,i);
    }
    for(int i=len-1;i>0;i--){
        int temp=an[0];
        an[0]=an[i];
        an[i]=temp;
        buildheap(an,i,0);
    }
}

归并排序

概念：

• 归并排序(mergesort)：是基于递归和分治策略的排序算法，其时间复杂度为O(nlogn)，但是归并排序不利于主存内排序，因为合并数组需要线性附加内存，如果N很大，则需要的表很大。
• 归并算法是将一个无序要排序的数组，将其分半，然后用递归，将数组一次次分半，然后利用递归到最后一层也就是数组无法再分了，递归返回时，开辟一个新数组，就用合并的操作将其有序的放入新数组，最后递归完毕就会得到一个有序的数组了。

合并操作：

• 对于某一个合并操作来讲(以合成升序数组为例，两个数组前提是要有序的)，我们将数组分成了A，B两个数组(其实并没有分成两个，只是用lpos，rpos记录这两个数组在原来数组的起始位置)，用leftend，rightend记录两个数组结尾的数组索引，然后我们开辟一个能存下A和B数组两个数组元素的数组
• 然后，我们将lpos位置的元素跟rpos位置的元素比较，哪个小就放进tempos位置上的新数组temarr中，如果lpos位置小，则将lpos位置元素赋值到temarr中的tempos位置上，tempos和lpos++，然后lpos++完的位置上的元素再跟rpos比较，重复之前操作。
• 直到一个数组元素全部赋值完后，如果另一个数组还有剩下元素，则将剩下的数组赋值到temarr中，则合并操作就结束了。

代码：

//合并操作
void merge(int*an,int *temarr,int lpos,int rpos,int rightend){
    int leftend=rpos-1;
    int nums=(rightend-lpos)+1;
    int tempos=lpos;
    //进行比较lpos和rpos位上的元素
    while (lpos<=leftend&&rpos<=rightend){
        if(an[lpos]<an[rpos]){
            temarr[tempos++]=an[lpos++];
        }else{
            temarr[tempos++]=an[rpos++];
        }
    }
    while (lpos<=leftend){       //处理left数组的剩余元素
        temarr[tempos++]=an[lpos++];
    }
    while (rpos<=rightend){     //处理right数组的剩余元素
        temarr[tempos++]=an[rpos++];
    }
    //使用rightend保证给an数组赋值的正确位置
    for(int i=0;i<nums;i++,rightend--){
        an[rightend]=temarr[rightend];
    }
}


//递归分治调用
void midsort(int* an,int *temarr,int left,int right){
    if(left<right){
        int center=(left+right)/2;
        midsort(an,temarr,left,center);
        midsort(an,temarr,center+1,right);
        merge(an,temarr,left,center+1,right);
    }
}

//归并排序
void mergesort(int *an,int len){
    int *temarr=new int[len];
    midsort(an,temarr,0,len-1);
}

快速排序

概念：

• 快速排序(quicksort)：也是一种分治的递归算法，时间复杂度为O(nlogn)，是实践中最快的已知排序算法

• 对数组S的快速排序的具体操作是：

  1. 如果S中元素个数为0或1，则直接返回该数组
  2. 取S中任一元素v，称之为枢纽元(pivot)
  3. 将S-{v}(S中除去v的其余元素)分成两个不想交的集合：S₁={x∈S-{v}|x<=v}和S₂={x∈S-{v}|x>=v}.(这个操作就是分治操作，不断地递归取枢纽元将其分割为一个个小集合进行排序)
  4. 返回{quicksort(S₁)后，继随v，继而quicksort(S₂)}

• 对于元素小于等于20的数组我们成为小数组，当数组为小数组时，快速排序不如插入排序好，这种情况下使用插入排序而不是使用递归的快速排序，将会节省大约15%的运行时间(相对于自始至终使用快速排序)

选取枢纽元：

1. 随机选取法：一个比较安全的选取方法，通过使用随机数生成器进行随机产生枢纽元v，因为随机的枢纽元不可能总在接连不断地产生劣质的分割。但是随机数的生成时间比较长，无法降低算法的平均运行时间
2. 三数中值分割法：一个比较好的选取方法，我们使用数组的左端、右端和中心位置上的三个元素的中间值(就是排序后第二大的元素)作为枢纽元v。使用该选取方法消除了预排序输入的坏情形，并且减少了快速排序大约5%的运行时间

分割策略：

• 当数组中的元素互异时，在分割阶段，我们将枢纽元跟数组最右端的元素进行交换，让枢纽元离开分区域内。我们需要将小于枢纽元和大于枢纽元的元素分布在区域的左右边。
• 利用i指向最左边的元素，j指向倒数第二个位置(也就是交换后枢纽元的左边位置)，如果i指向的元素小于枢纽元，i就向右移动，如果j指向的元素大于枢纽元，j就向左边移动，直到当i指向的位置不小于枢纽元，j指向的位置不大于枢纽元，就将i，j位置上的元素交换，但不交换i，j，交换完各自向右向左移动一位。
• 重复上述的操作，直到i和j交错，也就是当i在j的右边一位，j在i的左边一位的时候，不进行移动与交换，然后将枢纽元指向的元素和i所指的元素进行交换
• 对于i或者j指向元素跟枢纽元相等时，i和j停止移动进行交换位置上的元素，然后各自向右向左移动一位。

代码：

• 在实际操作中，我们在选取枢纽元的操作中，已经将left，center，right位置上的元素排好序了，而right位置上的元素本身就比枢纽元大，我们**不直接交换center和right位置上的元素，而是交换center跟right-1上的元素，这样将会为后面根据枢纽元分割区域中少比较一位。**优化了算法的性能

void insertsort(int* an,int low,int high){
    for(int i=low+1;i<=high;i++){
        int temp=an[i];
        int j;
        for(j=i;j>0&&an[j-1]>temp;j--){
            an[j]=an[j-1];
        }
        an[j]=temp;
    }
}

//三数中值分割法选取枢纽元
int midian3(int *an,int left,int right){
    int center=(left+right)/2;
    if(an[left]>an[center]){
        swap(an[left],an[center]);
    }
    if(an[left]>an[right]){
        swap(an[left],an[right]);
    }
    if(an[center]>an[right]){
        swap(an[center],an[right]);
    }
    //因为上述操作已经满足an[left]<an[center]<an[right]，an[right]大于枢纽元，我不需要进行交换让其在比较一位
    //因此让枢纽元跟right-1位置交换，这样在排序时减轻了右边数组的压力
    swap(an[center],an[right-1]);
    return an[right-1];   //返回枢纽元
}

void Qsort(int* an,int left,int right){
    if(left+10<=right){
        int pivot=midian3(an,left,right);
        int i=left,j=right-1;
        for(;;){
            while (an[++i]<pivot){}
            while (an[--j]>pivot){}
            if(i<j){
                swap(an[i],an[j]);
            }else{
                break;
            }
        }
        swap(an[i],an[right-1]);
        Qsort(an,left,i-1);
        Qsort(an,i+1,right);
    }
    else{
        insertsort(an,left,right);
    }
}

//快速排序
void quicksort(int *an,int len){
    Qsort(an,0,len-1);
}

• 另一种快速排序，每一次递归，我们将数组最左端就当作枢纽元，还是左端left开始跟right指向的元素跟枢纽元的值比较，an[left]<枢纽元left++，an[right]>枢纽元right–，直到找到an[left]>枢纽元，an[right]<枢纽元的时候进行交换an[left]和an[right]，直到left==right，就将枢纽元(也就是最左端的元素)与left当前所在位置进行交换，使得枢纽元放在正确的位置，然后在以left为界限分治。

  void quicksort(int *an,int low,int high){
      int left=low,right=high;
      if(left<high) return;
      int temp=an[left];   //枢纽元
      while(left!=right){
          //找寻右边区域小于枢纽元的元素位置
          while(an[right]>=temp&&left<right){
              right--;
          }
          //找寻左边区域大于枢纽元的元素位置
          while(an[left]<=temp&&left<right){
              left++;
          }
          //将找到的进行交换使得左边区域小于枢纽元，右边区域大于枢纽元
          if(left<right){
              swap(an[left],an[right]);
          }
      }
      //将枢纽元换到正确的中间区域
      swap(an[low],an[left]);
      //以left也就是当前枢纽元所在位置为界限进行分治
      quicksort(an,low,left-1);
      quicksort(an,left+1,high);
  }
  

桶式排序

概念:

• 桶排序(Bucket sort)：桶排序是一个非比较排序方法，它的排序是典型的用空间换时间的方法，它的时间复杂度甚至可能是线性复杂度(O(n))。如果我们有N个整数，数的大小范围为1_M(或者0M-1),就可以根据数据大小范围创建一个空桶(可以看作数组)或者多个空桶，然后将数据分桶后，就可以将这些数据从头到尾输出，输出完就会发现数据已经排好序了！时间复杂度为O(M+N)

注意事项：

• 该类算法是典型的空间换时间，要注意空间的开销
• 该类算法排序的对象必须是整数，如果是浮点数和自定义类数据比较，就无法使用该类排序方法。
• 分完桶之后，排序的算法自行选择
• 分桶规则，根据数据自定义映射规则。

计数排序

概念：

• 假设要排序的数据为N个整数，数的大小范围为0~M-1,我们就创建一个空桶(数组)，数组的长度为该数据的最大值(将每一个元素看作是数组的下标,例如元素1就放在数组a[1]中)，数组的值全部初始化为0，然后利用循环如果出现一个元素，就将其对应数组的下标中的数据+1(例如有数据中1出现了两次，则a[1]==2)，然后再将根据排序方式将数组元素顺序/逆序打印，对应数组下标的值为多少就打印几次。该排序方法时间复杂度为O(n)。

注意事项：

• 元素一定要为整数且为正数！

代码：

//计数排序
void CountSort(int *an,int len) {
    int max=an[0];
    for(int i=0;i<len;i++){
        if(an[i]>max){
            max=an[i];
        }
    }
    int arr[max+1];
    memset(arr,0,sizeof(int)*(max+1));
    for(int i=0;i<len;i++){
        arr[an[i]]++;
    }
    int j=0;
    for(int i=0;i<max+1;i++){
        while (arr[i]>0){
            an[j]=i;
            arr[i]--;
            j++;
        }
    }
}

基数排序

概念：

• 当数据范围过大的时候，如果使用桶排序则需要创建的空桶太多了，因此我们使用多趟桶式排序—我们将会用最低(有效)位优先的方式进行桶式排序。
• 首先我们得先创建一个0-9的桶(线性表)，我们将会将数据分趟次(根据数据最大数的位次)排序，第一次就以每个数据的最低位排序依次放到其最低位对应的桶中，例如：数据231就放在数组a[2]中，然后再根据次低位进行第二趟排序，如果只有一位数的数据就根据第一趟排序的顺序依次放在第0位的桶中，然后如果还有百位的数据则就继续第三趟排序。
• 时间复杂度为O(n)

注意事项：

• 数据一定得是整数。
• 如果数据出现负数，则需要数组每个元素先加上最小值的绝对值，然后排序完后再减去最小值的绝对值就能实现负数也能排序。
• 该算法是基于计数排序的，所以会使用到计数排序的排序方法

代码：

void countsort(int *an,int len,int exp){
    int count[10]={0};  //计数数组
    int ret[len];  //结果数组
    for(int i=0;i<len;i++){
        count[(an[i]/exp)%10]++;
    }
    for(int i=1;i<10;i++){
        count[i]+=count[i-1];
    }
    //这个地方需要从尾遍历到头，因为如果从头遍历到尾时，我们就无法确定前面出现的数的正确位置！！！
    for(int i=len-1;i>=0;i--){
        ret[count[(an[i]/exp)%10]-1]=an[i];
        count[(an[i]/exp)%10]--;
    }
    for(int i=0;i<len;i++){
        an[i]=ret[i];
    }
}

void RadixSort(int *an,int len){
    int max=an[0];
    for(int i=1;i<len;i++){
        if(an[i]>max){
            max=an[i];
        }
    }
    //通过最大数的位数对数据分趟桶式排序
    for(int k=1;max/k>0;k*=10){
        countsort(an,len,k);
    }
}

能够对负数排序的改进基数排序代码：

//基数排序
void countsort(int *an,int len,int exp){
    int count[10]={0};  //计数数组
    int ret[len];  //结果数组
    for(int i=0;i<len;i++){
        count[(an[i]/exp)%10]++;
    }
    for(int i=1;i<10;i++){
        count[i]+=count[i-1];
    }
    //这个地方需要从尾遍历到头，因为如果从头遍历到尾时，我们就无法确定前面出现的数的正确位置！！！
    for(int i=len-1;i>=0;i--){
        ret[count[(an[i]/exp)%10]-1]=an[i];
        count[(an[i]/exp)%10]--;
    }
    for(int i=0;i<len;i++){
        an[i]=ret[i];
    }
}

void RadixSort(int *an,int len){
    int max=an[0];
    int min=an[0];
    for(int i=1;i<len;i++){
        if(an[i]>max){
            max=an[i];
        }
        if(an[i]<min){
            min=an[i];
        }
    }
    for(int i=0;i<len;i++){
        an[i]+=abs(min);
    }
    //根据位数进行分趟桶式排序
    for(int k=1;max/k>0;k*=10){
        countsort(an,len,k);
    }
    for(int i=0;i<len;i++){
        an[i]-=abs(min);
    }
}

尾言

完整版笔记也就是数据结构与算法专栏完整版可到我的博客进行查看，或者在github库中自取(包含源代码)

• 博客1： codebooks.xyz
• 博客2：moonfordream.github.io
• github项目地址：Data-Structure-and-Algorithms