内部排序总结



一、内部排序

1、分类

（1）插入类排序：直接插入排序、希尔排序

（2）交换类排序：冒泡排序、快速排序

（3）选择类排序：简单选择排序、堆排序

（4）归并类排序：归并排序

（4）分配类排序：基数排序

可能每种里面还有很多，我把一些比较常见我要分析和实现的列上去了，大家可以自己再添加；

二、内部排序分析和实现

实现原理：

（1）将一个需要排序的数组分为两个部分，前半部分是已经排好序的，而后半部分是待排序的；

（2）最开始的时候，我们将第一个元素看为已经有序，因为一个元素不需要排序，所以最开始未排序的第一个数据是原始数组的第二个数据；

（3）然后我们从这待排序位置为i元素的前面的一个位置为i-1的元素开始往前一一查找i这个元素应该放在哪个合适的位置上，只有当这个待排序的元素大于往前遍历的下标变量对应的元素时，这个下标才往前挪，表示还没找到合适的位置，还有可能前面还有一些比它还大的；同时，我们需要把当前的元素往后挪一个，因为当前的元素比要排序的元素大，所以它肯定在这个待排序的元素，所以把它往后挪一个位置，才能腾出一个位置给这个待插入的元素，这样就会出现一个问题，当往后挪元素的时候，我们的待排序的位置就会存储从前面挪过来的元素，原来存储的这个待排序的元素就会被覆盖，所以，我们需要在开始往前寻找合适位置的时候就应该用一个临时变量存储这个待排序的元素，等找到合适位置的时候不至于丢失。

（4）做完一趟（3）的过程，我们需要把待排序的下标变量往后挪一个，去处理下一个，前面都是已经排好序的了；这样把2-len位置上的元素都处理一遍，数组就会有序了。

代码实现：

void insertsort(int a[],int len)                        //len表示数组中的元素个数
{
 int i,j;                                                           //定义在这里，作用域就为整个函数
 for(i=1;i
 {
  int tmp=a[i];                                            //临时变量存储此时待排序的这个元素的值
  for(j=i-1;a[j]>tmp&&j>=0;j--)                //这里j>=0是为了防止再往前找合适的位置的时候发生越界
  {
   a[j+1]=a[j];                                            //每找到一个比待排序元素大的元素就往后挪
  }
j++;                                                        //跳出循环的条件是a[j]==tmp或者是j<0了，这个是比合适的位置  
a[j]=tmp;                                               //多往前走了一步，所以需要加回去
 }
}

（1）它也是插入类的一种，但是，它要比直接插入排序多了一个间隔数组，在直接插入排序中的间隔数为1，这样整个数组的元素都是一个组的，需要和前面已经排好的所有元素比较，而如果间隔数不为1，比如为3，那就是从3这个下标开始循环往后走的下标是要让后面的每个待排序的元素找到合适的位置，往前走的下标是找到与它同组，找到同组内合适位置进行插入，下标往前走的条件还是一样的，但是往前走，一次是走此时的间隔数大小了。

（2）这样不直接分成一个组而是分成几个组，让它们组内先有序，是因为这样小的元素会逐渐往前面集中，而大的元素，就往后集中，会让整个数组越来越有序，当然最后还是要用间隔数为1，也就是直接插入排序不跳跃的让每个元素都考虑到前边所有已排序的元素下，找到合适的位置，但是因为数组已经越来越有序，所以其实，这一趟要交换的就不多了。

（3）间隔数组里的数需要互素，不能为倍数，因为如果为倍数的话，就还是会分到同一组，每组里的数可能还是那些，我们需要让每次分组都不同，这样才能打乱原来的排序，让数组小的元素往前挪，大的元素往后挪，让数组越来越有序。。

（4）最后一定要用间隔数为1，也就是再走一次直接插入排序

结构图

                                   颜色相同的元素为一组，这个模拟的是间隔为3的分组情况；

代码实现：

#include
void shell(int a[],int len,int dk)//这里实现和插入排序没什么区别，但是每次往前挪的变量一次都是挪间隔数个
{
 int i,j;
 for(i=dk;i
 {
  int tmp=a[i];
  for(j=i-dk;tmp
  {
    a[j+dk]=a[j];
  }
 j+=dk;
 a[j]=tmp;
 }

}

void shellsort(int a[],int a_len,int b[],int b_len)
{
    for(int i=0;i
      shell(a,a_len,b[i]);
}

int main()
{
 int a[10]={10,9,8,7,6,5,4,3,2,1};
 int b[3]={5,3,1};                             //b是间隔数组，这里面的间隔数我们都需要走一遍
 shellsort(a,10,b,3);
 return 0;
}

（1）堆定义：n个关键字序列Kl，K2，…，Kn称为大根堆，当且仅当该序列满足如下性质：(1)ki>=k(2i）且ki>=k(2i+1)(1≤i≤ n），(即父亲大于儿子), 则称为大根堆；如果ki<=k(2i+1)(1≤i≤ n），则成为小根堆。

（2）初建堆，我们最开始先要把堆建起来，其实这个过程不需要我们做什么，堆是一种结构，我们把一个数组想象成堆，然后根据这个结构的关系读取相应的下标元素；例如：如果我们要访问i的左孩子，那就是访问2i这个下标的元素，如果要考虑访问右孩子，那么就是就是2i+1,如果我们想要访问i结点的父节点，那么就是对i/2取整就行了，这是堆里通过父节点找子节点或者通过子节点找父节点的方法；

（3）调整堆，我们可以通过传入父亲节点进去，把以他为根节点的这个堆变成大根堆，我们这个调整堆的思想是从上往下的，把父亲节点和较大的那个孩子节点比较，如果父亲节点大就不需要动，如果孩子节点较大，就需要交换位置，让大的孩子节点成为父亲节点，原来的父亲节点移到孩子节点的位置，这时候还没有完，还得往下走，因为可能它还小于以它为父亲节点的左右孩子节点，如果一直小，就要一直交换，直到走到叶子节点，到叶子节点了，就说明它已经在最后一层了，它的下面没有数据了，它放在了该放的位置了。

（4）在排序之前我们利用（3）中的操作步骤，从最后一个父亲节点开始调整，直到根节点；这样从下往上调整的原因是，我们每个父亲节点经过（3），它这个节点包括它的左右孩子的这个小堆就已经是个大根堆了，这样如果往上走，上面的某个节点需要调整，我们只要沿着它交换的那条线路进行调整就可以了，不用考虑其他未交换的部分，因为它们没有变动，所以还是大根堆，这样就省了很多麻烦。

（5）堆排序一般是从数组一号下标开始，所以零号位置一般不用

（6）如果小根堆的话实现的就是逆序，步骤和上面解决大根堆是一样，只是交换条件是根节点比孩子节点大的时候，因为小根堆保证根节点最小

（7）根据上述步骤排好序后，我们每次把第一个位置和堆的最后一个位置交换，因为第一个位置是最大的（大根堆），把它放在最后，再把第一个节点作为根节点，然后进行堆调整，让它恢复大根堆，做除去0号下标的个数再减一次就可以了，因为当n-1个排好序了，则最后一个就在它对应的位置了，就不用再排了。

结构图

                                                                               大根堆

                                                                            小根堆

代码实现

#include
void heapadjust(int a[],int i,int len)
{
 for(int j=2*i;j
 {
  if(j+1<=len&&a[j+1]>a[j]) j++;

  if(a[j]>a[i])
  {
   int tmp=a[j];
   a[j]=a[i];
   a[i]=tmp;
  }
  i=j;
 }
}

void heapsort(int a[],int len)
{
 for(int i=len/2;i>1;i--)
 {
  heapadjust(a,i,len);
 }

 for(int i=len;i>1;i--)
 {
  int tmp=a[1];
  a[1]=a[i];
  a[i]=tmp;
  heapadjust(a,1,i-1);
 }
}

int main()
{
 int a[10]={-1,9,8,7,6,5,4,3,2,1};
 heapsort(a,9);
 for(int i=0;i<10;i++)
  printf("%d ",a[i]);
 return 0;
}

（1）用一个下标变量i，把数组遍历一遍，做外层循环把，为每一个位置找到合适的数据，内存循环j没次都从i+1的元素开始遍历到结尾，在剩下没排序的元素中找出第i+1小的元素（因为有0号小标，所以下标会比实际少一），放在第i号位置上；

（2）用一个变量mid保存最小值的下标，初值赋值为i的下标，每次为找到放在i下标的合适位置，都用j把剩下没排序的数据遍历一遍，当此时遍历到的这个元素的值小于记录的最小下标对应的最小值时，就把记录最小的下标变量mid赋值为此时的j；

（3）然后每次用j遍历一遍找到最小的值的小标，如果要放的下标位不是mid找到的最小值的位置，就把两个数据交换位置；

（4）这样每次把未排序的数据中最小的元素选出来放在合适的位置上，做n-1次就够了，因为当n-1个都在它们合适的位置上时，最后一个元素也在它的合适的位置上了，这个元素就不用排了；

代码实现

void selectsort(int a[],int len)
{
 for(int i=0;i
 {
  int mid =i;
  for(int j=i+1;j
   if(a[j]
  
  if(mid!=i)
  {
   int tmp=a[i];
   a[i]=a[mid];
   a[mid]=tmp;
  }
 }
}

实现原理

（1）这个冒泡排序有点像我们小时候往往池塘流丢瓦片，打出水泡；我们定义一个变量j，每次从0都遍历到最后一个未排序的元素的上一个元素，因为我们每次都要和下一个元素比，所以要少一个；

（2）一旦这个元素比下个元素大，就把它和下一个元素交换；这样每次都能选出一个最大的，放在这一趟未排序的元素的最后；

（3）我们用一个变量i控制趟数，也是和上面一样，只要做n-1趟就够了，因为n-1个元素都在自己合适的位置的时候，最后一个元素也在自己合适的位置了。

代码实现：

void bubblesort(int a[],int len)
{
 for(int i=0;i
  for(int j=0;j
  {
   if(a[j]>a[j+1])
   {
    int tmp=a[j];
     a[j]=a[j+1];
    a[j+1]=tmp;
   }
  }
}

实现原理：

（1）基数排序又叫桶排序，我们每次准备十个桶，每个桶的大小是这个数组长度，因为可能取模之后，数组里的元素都在一个桶里，所以我们把每个桶的大小都定义到和数组的大小一样大，这里的桶其实呢就是我们的数组

（2）我们给每个桶（数组）从0-9开始编号，从头遍历数组，从取个位开始，个位数为多少，就把它放在几号桶里，每个桶都从0号坐标开始放；

（3）处理完个位数，就把桶从一号桶开始遍历，每个都是从零号下标开始，遍历到非零元素（我们初始化数组的时候把它们都置0，表示没有存放数据），就把它赋值到a数组中，a数组也是从0号下标开始，每存放一个把标记往后挪一个；

（4）处理完个位数就按上面步骤处理十位数，十位数为多少就把它放在哪个编号的桶，也就是按十位数排序，直到处理到最大的一位数的最高位，如果其他数没有这么高的的位就放在零号桶中；完成之后再把按照桶中的值按（3）步骤赋值给原数组，就完成排序了。

过程图：

代码实现：

int getbit(int a[],int len)                                                  //得到最大数有几位数字，决定了要做几趟(2)(3)
{                                                                                      
 int max=0;
 for(int i=1;i
  if(a[i]>a[max])
   max=i;

 int m=a[max];
 max=0;
 while(m>0)
 {
  m/=10;
  max++;
 }

 return max;
}
int getb(int x,int j)                                                               //得到x从右数起的第j位数字
{
 
 while(j-->0)
 {
  x/=10;
 }

 return x;
}

void basesort(int a[],int len,int j)                                   //完成一趟（2）（3）
{
 int b[10][10]={0};
 int k;
 int count;
 for(int i=0;i
 {
  count=0;
  k=getb(a[i],j);
  while(b[k][count]!=0)
   count++;

  if(a[i]==0) 
     {
   b[k][count]=-1;
   count++;
  }

  else
  {
   b[k][count]=a[i];
   count++;
  }
 }

 
 int c=0;
 for(int i=0;i
 {
  count=0;
  while(b[i][count]!=0)
  {
   if(b[i][count]<0)
   {
    a[c]=0;
    c++;
   }
   else
   {
    a[c]=b[i][count];
    c++;
   }
   count++;
  }
 }
}
int main()                                                               //做最大数的总位数次（2）（3），就能完成排序
{
   int a[10]={3,2,65,56,57,57,98,1,0,54};
   for(int i=0;i
   {
    basesort(a,10,i);
   }

   return 0;
}

7、归并排序
实现原理：

（1）既然叫归并排序，就体现了一个分和归并的过程；我们先要把组里的元素进行二分，这里的二分凭的是实际存储物理的中间位置，待会说的快速排序，是逻辑上的中间位置；我们把一组元素，从中间位置分成两组，再把两组中的每组分为两组，一直分到，每个元素单独为一组就停止；

（2）分完之后我们就应该按照分的过程再合并回去。原来分出来的两组合并起来，给两个下标变量分别标记两个要合并的组，假设一个为i，一个为j，定义一个中间数组，存储两个组合并后的结果，i, j都从两个要合并的组的开始位置开始，如果i下标对应的值下标要小于j下标对应的值，那么就把i对应的值放在对应的临时数组的i位置（因为我们的临时数组大小定义的和原来排序数组一样大小，我们大多数都是部分合并，也就是让部分有序，这样把临时数组合并的有序的部分赋值回去到相应的位置的时候也符合我们的想法，赋值回去的那一部分已经有序，只需要处理还未合并处理的部分），然后i++，再比较i对应的下标和j对应的下标的值，那个小就把哪个的值挪到临时数组里，按此反复，直到一个组已经处理完了，就把另外一组剩下的元素以此赋值到刚刚排序部分的尾部就好了；

（3）按照（2）步骤合并到最开始的数组长度，我们的归并排序就完成了；

过程图：

                 黑色代表分的过程，从上往下分的，红色代表和的过程，从下往上合并的；

代码实现：

#include
void merge(int a[],int tmp[],int start,int end)                                //归并并赋值到原来的数组
{
 int i=start;
 int j=(start+end)/2+1;
 int k=start;
 for(;i<(start+end)/2+1&&j
 {
  if(a[i]<=a[j]) tmp[k]=a[i++];
  else tmp[k]=a[j++];
 }

 while(i<=(start+end)/2)  tmp[k++]=a[i++];
 while(j<=end) tmp[k++]=a[j++];

 for(int i=start;i
 {
  a[i]=tmp[i];
 }
}

void mergesort(int a[],int tmp[],int start,int end)
{
 if(start
 {
  int mid=(start+end)/2;
  mergesort(a,tmp,start,mid);
  mergesort(a,tmp,mid+1,end);
  merge(a,tmp,start,end);
 }
}

int main()
{
 int a[]={15，13，11，5，64，1，35，27，98，45，39};
 int tmp[10]={};
 mergesort(a,tmp,0,11);
 return 0;
}