一些排序算法

佚名 6年前 (2019-02-26) 算法 1824人围观抢沙发百度已收录

输入：n个数的数<a₁,a₂,a₃,a₄>

输出：输人序列的一个排列(a₁,a₂,…，a_n)，满足a₁^’≤a₂^’≤…≤a_n^’

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

插入排序

书中用了一个很好的例子来描述插入算法的原理，像许多人排序自己手中的扑克牌。

排序一手扑克牌，开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每人从子上拿走一张牌并将它插入左手中正确的位置，我们从右到左将它与在手中的每张牌进行比较，拿在左手上的牌总是排序好的，只需将该牌插入到正确的位置。

书中将伪代码命名为INSERTION-SORT(A), 其中A为一个数组。该算法是原址排

序：算法在数组A中重排这些数，在任何

片候，最多只有其中的常数个数字存储在数组外在过程 INSERTION-SORT结束时，输入数组包含已排序的数组

下面给出的关于c++语言的实现

#include <iostream>

void insertion_sort(int a[],int n) // n为该数组的长度
{
  for (int j = 1; j <n ; j++)
  {
    int key = a[j];
    int i = j - 1;
    while (i >= 0 && a[i] > key)
    {
      a[i + 1] = a[i];
      i -= 1;
    }
    a[i + 1] = key;
  }
}
int main()
{
  int a[] = { 3,6,7,1,3 };
  insertion_sort(a,sizeof(a)/sizeof(a[0]));
  
}

该算法的执行情况：

递归排序

在归并算法中其实最重要的是一个名为MERGE（A，p，q，r）的函数。这主要对两个数组排序，合并成一个数组。实现的代码如下：

实现的原理相当于两堆扑克牌中，从继续小的里面拿牌，依次在排序。

#include <iostream>
void merge(int a[], int p, int q, int r); //这里的函数都是以下标为参数，不是以个数开始的
void merge_sort(int a[], int p, int r);
int main()
{
  int a[] = { 3,5,6,13,14,1,100,53232 }; 
 // merge(a, 0, 4, 7);
  merge_sort(a, 0, 7);
}

void merge(int a[], int p, int q, int r)
{
  int n1 = q-p + 1; // [p,q]
  int n2 = r - q;// (q,r]
  int* Rarray =new int[n1];
  int* Larray = new int[n2];
  for (int i = 0; i <n1; i++)
  {
    Rarray[i] = a[p+i];
  }
  for (int i = 0; i <n2; i++)
  {
    Larray[i] = a[q +1+ i];
  }
  int k = p;
  int i = 0; 
  int j = 0; 
  for (k; k<=r; k++)
  {
    if (i >= n1)
    {
      a[k] = Larray[j++];
      continue;
    }
    if (j >= n2)
    {
      a[k] = Rarray[i++];
      continue;
    }
    if (Rarray[i]<=Larray[j])
    { 
      a[k] = Rarray[i++];
    }
    else
    {
      a[k] = Larray[j++];   
    }
  } 
}
void merge_sort(int a[], int p, int r)
{
  if (p < r) {
    int q = (p + r) / 2;
    merge_sort(a, p, q);
    merge_sort(a, q + 1, r);
    merge(a, p,q , r);
  }
}