求逆序对

【例题4】光荣的梦想1635

题目描述 Description

Minimum Inversion Number
Time Limit: 2000/1000 MS
(Java/Others)    Memory Limit:
65536/32768 K (Java/Others)
Total Submission(s): 6743    Accepted Submission(s): 4112

7种常用的排序算法总结

Description:Prince对他在这片大陆上维护的秩序感到满意,于是决定启程离开艾泽拉斯。在他动身之前,Prince决定赋予King_Bette最强大的能量以守护世界、保卫这里的平衡与和谐。在那个时代,平衡是个梦想。因为有很多奇异的物种拥有各种不稳定的能量,平衡瞬间即被打破。KB决定求助于你,帮助他完成这个梦想。
  一串数列即表示一个世界的状态。
  平衡是指这串数列以升序排列。而从一串无序数列到有序数列需要通过交换数列中的元素来实现。KB的能量只能交换相邻两个数字。他想知道他最少需要交换几次就能使数列有序。

给定一个序列a1,a2,…,an,如果存在i<j并且ai>aj,那么我们称之为逆序对,求逆序对的数 

 

 2016.04.30  Poetry  Algorithm

Input:第一行为数列中数的个数n,第二行为n <=
10000个数。表示当前数列的状态。

数据范围:N<=105。Ai<=105。时间限制为1s

Problem Description
The inversion number of a given number sequence a1, a2, …, an is the
number of pairs (ai, aj) that satisfy i < j and ai > aj.

排序算法:一种能将一串数据依照特定的排序方式进行排列的一种算法。

Output:输出一个整数,表示最少需要交换几次能达到平衡状态。

输入描述 Input Description

For a given sequence of numbers a1, a2, …, an, if we move the first m
>= 0 numbers to the end of the seqence, we will obtain another
sequence. There are totally n such sequences as the following:

排序算法性能:取决于时间和空间复杂度,其次还得考虑稳定性,及其适应的场景。

Sample Input

第一行为n,表示序列长度,接下来的n行,第i+1行表示序列中的第i个数。

a1, a2, …, an-1, an (where m = 0 – the initial seqence)
a2, a3, …, an, a1 (where m = 1)
a3, a4, …, an, a1, a2 (where m = 2)

an, a1, a2, …, an-1 (where m = n-1)

稳定性:让原本有相等键值的记录维持相对次序。也就是若一个排序算法是稳定的,当有俩个相等键值的记录R和S,且原本的序列中R在S前,那么排序后的列表中R应该也在S之前。

求逆序对。  4

输出描述 Output Description

You are asked to write a program to find the minimum inversion number
out of the above sequences.

1-冒泡排序

  2 1 4 3

所有逆序对总数.

 

原理

Sample
Output:2

样例输入 Sample Input

Input
The input consists of a number of test cases. Each case consists of two
lines: the first line contains a positive integer n (n <= 5000); the
next line contains a permutation of the n integers from 0 to n-1.

俩俩比较相邻记录的排序码,若发生逆序,则交换;有俩种方式进行冒泡,一种是先把小的冒泡到前边去,另一种是把大的元素冒泡到后边。冒泡法大家都较熟悉。其原理为从a[0]开始,依次将其和后面的元素比较,若a[0]>a[i],则交换它们,一直比较到a[n]。同理对a1,a2,…a[n-1]处理,即完成排序

【分析】

4

 

冒泡排序的基本概念:

1.原始的解决方案(双重循环)

3

Output
For each case, output the minimum inversion number on a single line.

依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,将最大的数放到了最后。在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的),第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。如此下去,重复以上过程,直至最终完成排序。由于在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序。

C:=0;

2

 

实现:

For i:=1 to n
-1 do

3

Sample Input
10
1 3 6 9 0 8 5 7 4 2

外循环变量设为i,内循环变量设为j。假如有10个数需要进行排序,则外循环重复9次,内循环依次重复9,8,…,1次。每次进行比较的两个元素都是与内循环j有关的,它们可以分别用a[j]和a[j+1]标识,i的值依次为1,2,…,9,对于每一个i,j的值依次为1,2,…10-i。

       for j:=i+1 to n do if
a[i]>a[j] then c:=c+1;

2

Sample Output
16

图示:

时间复杂度为O(n2)

样例输出 Sample Output

Author
CHEN, Gaoli
 

性能

2.采用二分法求解:

3

Source
ZOJ Monthly, January 2003
 

时间复杂度为O(N^2),空间复杂度为O(1)。排序是稳定的,排序比较次数与初始序列无关,但交换次数与初始序列有关。

记数列a[st,ed]的逆序对数目为D(st,ed);

代码:

Recommend
Ignatius.L
 

题意:
一个由0..n-1组成的序列,每次可以把队首的元素移到队尾,
          求形成的n个序列中最小逆序对数目
 
思路:
如果求出第一种情况的逆序列,其他的可以通过递推来搞出来,一开始是t[1],t[2],t[3]….t[N]

优化

    mid=[(st+ed)/2],则有:

#include<iostream>

它的逆序列个数是N个,如果把t[1]放到t[N]后面,逆序列个数会减少t[1]个,相应会增加N-(t[1]+1)个 

若初始序列就是排序好的,对于冒泡排序仍然还要比较O(N^2)次,但无交换次数。可根据这个进行优化,设置一个flag,当在一趟序列中没有发生交换,则该序列已排序好,但优化后排序的时间复杂度没有发生量级的改变

   
D(st,ed)=D(st,mid)+D(mid+1,ed)+F(st.mid,ed).

#include<cstdlib>

 

代码

其中F(st,mid,ed)表示一个数取自A[st,mid],令一个数取自A[mid+1,ed]的逆序对数目。

using namespace std;

暴力法300ms:

#include

若要求计算d值的同时数列A已排序,设I,j指针分别已排序的A[st,med)和A(mid+1,ed)中的一个元素,若满足:

int a[100011],zh[100011];

[cpp]
#include<stdio.h>  
int a[5555]; 
int main() 

    int n,i,j,ans=999999999; 
    while(scanf(“%d”,&n)!=EOF) 
    { 
        ans=999999999; 
           for(i=0;i<n;i++) scanf(“%d”,&a[i]); 
           int cnt=0; 
           for(i=0;i<n;i++) 
               for(j=i+1;j<n;j++) 
               { 
                   if(a[i]>a[j]) cnt++; 
               } 
           // printf(“cnt=%dn”,cnt);  
           if(ans>cnt)  ans=cnt; 
           for(i=0;i<n;i++) 
           { 
               cnt=cnt-a[i]+n-1-a[i]; 
               if(ans>cnt)  ans=cnt; 
            } 
           printf(“%dn”,ans); 
    } 
    return 0; 

void sort(int *a,int len)

A[mid+1],…A[j-1]均小于A[i],但A[j]>A[i]

unsigned long long k;

#include<stdio.h>
int a[5555];
int main()
{
    int n,i,j,ans=999999999;
    while(scanf(“%d”,&n)!=EOF)
    {
        ans=999999999;
           for(i=0;i<n;i++) scanf(“%d”,&a[i]);
           int cnt=0;
           for(i=0;i<n;i++)
               for(j=i+1;j<n;j++)
               {
                   if(a[i]>a[j]) cnt++;
               }
           // printf(“cnt=%dn”,cnt);
           if(ans>cnt)  ans=cnt;
           for(i=0;i<n;i++)
           {
               cnt=cnt-a[i]+n-1-a[i];
               if(ans>cnt)  ans=cnt;
            }
           printf(“%dn”,ans);
    }
    return 0;
}

{

则j-mid-1必须计入F,顺序移动I,j指针即可完成合并。

void mergesoft(int left,int right)         

下面说一下线段树的做法  31ms
用线段树去求输入序列的逆序数
方法:
把树的叶子节点作为每个数的对应位置
枚举到第i个数时,我们需要求出前i次插入的数中有多少个比a[i]大,
即去寻找已经插入的数中比a[i]大的数的个数 
即查询叶子节点a[i]到n的数的个数

    int i,j,t;

#include<iostream>

{

[cpp]
#include<stdio.h>  
int a[10000]; 
struct haha 

    int left; 
    int right; 
    int num; 
}node[10000*4]; 
void build(int left,int right,int nd) 

    node[nd].left=left; 
    node[nd].right=right; 
    node[nd].num=0; 
    if(left==right)  
    { 
        return ; 
    } 
    int mid=(left+right)/2; 
    build(left,mid,nd*2); 
    build(mid+1,right,nd*2+1); 

int query(int left,int right,int nd) 

    int mid=(node[nd].left+node[nd].right)/2; 
    if(node[nd].left==left&&node[nd].right==right) 
    { 
        return node[nd].num; 
    } 
 
    if(right<=mid) 
    { 
          return query(left,right,nd*2); 
    } 
    else if(left>mid) 
    { 
        return query(left,right,nd*2+1); 
    } 
    else 
    { 
        return query(left,mid,nd*2)+query(mid+1,right,nd*2+1); 
    } 

void update(int pos,int nd) 

      
    if(node[nd].left==node[nd].right) {node[nd].num++;return ;} 
     
    int mid=(node[nd].left+node[nd].right)/2; 
    if(pos<=mid)  update(pos,nd*2); 
    else update(pos,nd*2+1); 
    node[nd].num=node[nd*2].num+node[nd*2+1].num; 

int main() 

    int n,i,j; 
    while(scanf(“%d”,&n)!=EOF) 
    { 
          for(i=0;i<n;i++) 
              scanf(“%d”,&a[i]); 
          build(0,n-1,1); 
          int sum=0; 
          for(i=0;i<n;i++) 
          { 
              //printf(“i=%d  sum=%dn”,i,sum);  
              sum+=query(a[i],n-1,1); 
             // printf(“>>>”);  
              update(a[i],1); 
          } 
         // printf(“%dn”,sum);  
          int ans=99999999; 
          if(ans>sum)  ans=sum; 
           for(i=0;i<n;i++) 
           { 
               sum=sum-a[i]+n-1-a[i]; 
               if(ans>sum) ans=sum; 
           } 
 
               printf(“%dn”,ans); 
    } 
    return 0; 

    for( i = 0;i

using
namespace std;

     if(left==right) return;

#include<stdio.h>
int a[10000];
struct haha
{
    int left;
    int right;
    int num;
}node[10000*4];
void build(int left,int right,int nd)
{
    node[nd].left=left;
    node[nd].right=right;
    node[nd].num=0;
    if(left==right)
    {
        return ;
    }
    int mid=(left+right)/2;
    build(left,mid,nd*2);
    build(mid+1,right,nd*2+1);
}
int query(int left,int right,int nd)
{
    int mid=(node[nd].left+node[nd].right)/2;
    if(node[nd].left==left&&node[nd].right==right)
    {
        return node[nd].num;
    }

    {

int
temp[10001],a[10001],tot=0;

     int mid=(left+right)/2;

    if(right<=mid)
    {
          return query(left,right,nd*2);
    }
    else if(left>mid)
    {
        return query(left,right,nd*2+1);
    }
    else
    {
        return query(left,mid,nd*2)+query(mid+1,right,nd*2+1);
    }
}
void update(int pos,int nd)
{
    
    if(node[nd].left==node[nd].right) {node[nd].num++;return ;}
   
    int mid=(node[nd].left+node[nd].right)/2;
    if(pos<=mid)  update(pos,nd*2);
    else update(pos,nd*2+1);
    node[nd].num=node[nd*2].num+node[nd*2+1].num;
}
int main()
{
    int n,i,j;
    while(scanf(“%d”,&n)!=EOF)
    {
          for(i=0;i<n;i++)
              scanf(“%d”,&a[i]);
          build(0,n-1,1);
          int sum=0;
          for(i=0;i<n;i++)
          {
              //printf(“i=%d  sum=%dn”,i,sum);
              sum+=query(a[i],n-1,1);
             // printf(“>>>”);
              update(a[i],1);
          }
         // printf(“%dn”,sum);
          int ans=99999999;
          if(ans>sum)  ans=sum;
           for(i=0;i<n;i++)
           {
               sum=sum-a[i]+n-1-a[i];
               if(ans>sum) ans=sum;
           }

        for(j = 0;j

void
merge_sort(int left,int right)

     mergesoft(left,mid);mergesoft(mid+1,right);      

               printf(“%dn”,ans);
    }
    return 0;
}
下面是归并排序方法:

        {

{
if(left==right)return;

     int p=left,q=left,j=mid+1;

套用归并排序模板

            if(a[j] >a[j+1])

  int mid=(left+right)/2;

     while(p<=mid && j<=right)

[cpp]
#include<stdio.h>  
#include<malloc.h>  
int ans,a[5050],b[5050]; 
void merge(int left,int mid,int right) 

    int i,j,cnt=0; 
    int *p; 
    p=(int *)malloc((right-left+1)*sizeof(int)); 
    i=left; 
    j=mid+1; 
    while(i<=mid&&j<=right)//这时候i 和 j 指向的部分都排序完毕了
现在合并  
    { 
        if(a[i]<=a[j]) 
        { 
            p[cnt++]=a[i]; 
            i++; 
        } 
        else 
        { 
            p[cnt++]=a[j]; 
            j++; 
            ans+=mid-i+1;//第i个比j大 由于i已经从小到大排过序了
那么i+1到mid的也会比j大  
        } 
    } 
    while(i<=mid) 
    { 
        p[cnt++]=a[i++]; 
    } 
    while(j<=right) 
    { 
        p[cnt++]=a[j++]; 
    } 
    cnt=0; 
    for(i=left;i<=right;i++) 
        a[i]=p[cnt++]; 
    free(p); 
 

void merge_sort(int left,int right) 

    if(left<right) //长度大于1  这是个判断不是循环  
    { 
        int mid; 
        mid=(left+right)/2; 
        merge_sort(left,mid); 
        merge_sort(mid+1,right); 
        merge(left,mid,right); 
    } 

 
int main() 

    int n,i,j ; 
    while(scanf(“%d”,&n)!=EOF) 
    { 
 
    for(i=0;i<n;i++) {scanf(“%d”,&a[i]);b[i]=a[i];} 
        ans=0; 
        merge_sort(0,n-1); 
        //printf(“ans=%dn”,ans);  
        int cnt=999999999; 
        if(cnt>ans) cnt=ans; 
 
           for(i=0;i<n;i++) 
           { 
               //printf(“a[i]=%dn”,a[i]);  
               ans=ans-b[i]+n-1-b[i]; 
               if(cnt>ans)  cnt=ans; 
            } 
           printf(“%dn”,cnt); 
    } 
    return 0; 

            {

  merge_sort(left,mid);

     {

#include<stdio.h>
#include<malloc.h>
int ans,a[5050],b[5050];
void merge(int left,int mid,int right)
{
    int i,j,cnt=0;
    int *p;
    p=(int *)malloc((right-left+1)*sizeof(int));
    i=left;
    j=mid+1;
    while(i<=mid&&j<=right)//这时候i 和 j 指向的部分都排序完毕了
现在合并
    {
        if(a[i]<=a[j])
        {
            p[cnt++]=a[i];
            i++;
        }
        else
        {
            p[cnt++]=a[j];
            j++;
            ans+=mid-i+1;//第i个比j大 由于i已经从小到大排过序了
那么i+1到mid的也会比j大
        }
    }
    while(i<=mid)
    {
        p[cnt++]=a[i++];
    }
    while(j<=right)
    {
        p[cnt++]=a[j++];
    }
    cnt=0;
    for(i=left;i<=right;i++)
        a[i]=p[cnt++];
    free(p);

                t  = a[j];

  merge_sort(mid+1,right);

          if(a[p]>a[j])

}
void merge_sort(int left,int right)
{
    if(left<right) //长度大于1  这是个判断不是循环
    {
        int mid;
        mid=(left+right)/2;
        merge_sort(left,mid);
        merge_sort(mid+1,right);
        merge(left,mid,right);
    }
}

                a[j] = a[j+1];

  int p=left,i=left,j=mid+1;

          {k=k+mid-p+1;zh[q++]=a[j++];}   

int main()
{
    int n,i,j ;
    while(scanf(“%d”,&n)!=EOF)
    {

                a[j+1] = t;

  while(i<=mid&&j<=right)

          else

    for(i=0;i<n;i++) {scanf(“%d”,&a[i]);b[i]=a[i];}
        ans=0;
        merge_sort(0,n-1);
        //printf(“ans=%dn”,ans);
        int cnt=999999999;
        if(cnt>ans) cnt=ans;

            }

{

           zh[q++]=a[p++];

           for(i=0;i<n;i++)
           {
               //printf(“a[i]=%dn”,a[i]);
               ans=ans-b[i]+n-1-b[i];
               if(cnt>ans)  cnt=ans;
            }
           printf(“%dn”,cnt);
    }
    return 0;
}

        }

if(a[i]>a[j])
{ tot=tot+mid-i+1;temp[p++]=a[j++]; }

     }

 

    }

            else temp[p++]=a[i++];

     while(p<=mid) zh[q++]=a[p++];

}

    }

     while(j<=right) zh[q++]=a[j++];

void main()

   
while(i<=mid)temp[p++]=a[i++];

     for(int i=left;i<=right;i++) a[i]=zh[i];

{

   
while(j<=right)temp[p++]=a[j++];

}

    int a[6] = {10,2,8,-8,11,0};

    for(i=left;i<=right;i++)
a[i]=temp[i];

int main()

    int i = 0;

}

{

    sort(a,6);

int
main()

    int n;cin>>n;

    for(i = 0; i<6;++i)

{  int n;

    for(int i=1;i<=n;i++) cin>>a[i];

    {

   cin>>n;

    mergesoft(1,n);

        printf(“%d “,a[i]);

   for(int i=1;i<=n;i++)
cin>>a[i];

    cout<<k;

    }

   merge_sort(1,n);

    return 0;

    printf(“n”);

   cout<<tot; 

}

}

   return 0;

 

冒泡法原理简单,但其缺点是交换次数多,效率低。下面介绍一种源自冒泡法但更有效率的方法“选择法”。

}

 

2-选择排序

原理

每次从未排序的序列中找到最小值,记录并最后存放到已排序序列的末尾.选择法循环过程与冒泡法一致,它还定义了记号k=i,然后依次把a[k]同后面元素比较,若a[k]>a[j],则使k=j.最后看看k=i是否还成立,不成立则交换a[k],a[i],这样就比冒泡法省下许多无用的交换,提高了效率。

性能

时间复杂度为O(N^2),空间复杂度为O(1),排序是不稳定的(把最小值交换到已排序的末尾导致的),每次都能确定一个元素所在的最终位置,比较次数与初始序列无关。

代码

//直接选择排序

#include

void sort(int *a,int len)

{

int i,j,min,t;

for(i = 0;i

{

for(min=i,j=i+1;j

{

if(a[min]>a[j])

min = j;

}

if(min!=i)

{

t = a[i];

a[i] = a[min];

a[min] = t;

}

}

}

void main()

{

int a[6] = {4,0,3,2,5,1};

sort(a,6);//a代表数组的首地址

for(int i=0;i<6;++i)

printf(“%dn”,a[i]);

}

选择法比冒泡法效率更高,但说到高效率,非“快速法”莫属,现在就让我们来了解它。

3-快速排序

原理

基本思想:

快速排序是对冒泡排序的一种改进。由C. A. R.
Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

实现:

设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。

一趟快速排序的算法是:

1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;

2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0];

3)从j开始向前搜索,即由后开始向前搜索(j –
),找到第一个小于key的值A[j],A[i]与A[j]交换;

4)从i开始向后搜索,即由前开始向后搜索(i ++
),找到第一个大于key的A[i],A[i]与A[j]交换;

5)重复第3、4、5步,直到 I=J;
(3,4步是在程序中没找到时候j=j-1,i=i+1,直至找到为止。找到并交换的时候i,
j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。)

图示:

举例说明:

如无序数组[6 2 4 1 5 9]

a),先把第一项[6]取出来,

用[6]依次与其余项进行比较,

如果比[6]小就放[6]前边,2 4 1 5都比[6]小,所以全部放到[6]前边

如果比[6]大就放[6]后边,9比[6]大,放到[6]后边,//6出列后大喝一声,比我小的站前边,比我大的站后边,行动吧!霸气十足~

一趟排完后变成下边这样:

排序前 6 2 4 1 5 9

排序后 2 4 1 5 6 9

b),对前半拉[2 4 1 5]继续进行快速排序

重复步骤a)后变成下边这样:

排序前 2 4 1 5

排序后 1 2 4 5

前半拉排序完成,总的排序也完成:

排序前:[6 2 4 1 5 9]

排序后:[1 2 4 5 6 9]

性能

快排的平均时间复杂度为O(NlogN),空间复杂度为O(logN),但最坏情况下,时间复杂度为O(N^2),空间复杂度为O(N);且排序是不稳定的,但每次都能确定一个元素所在序列中的最终位置,复杂度与初始序列有关。

优化

当初始序列是非递减序列时,快排性能下降到最坏情况,主要因为基准每次都是从最左边取得,这时每次只能排好一个元素。

所以快排的优化思路如下:

优化基准,不每次都从左边取,可以进行三路划分,分别取最左边,中间和最右边的中间值,再交换到最左边进行排序;或者进行随机取得待排序数组中的某一个元素,再交换到最左边,进行排序。

在规模较小情况下,采用直接插入排序

代码

//快速排序

#include

int FindPos(int * a, int low, int high)

{

int val = a[low];

while (low < high)

{

while (low=val)

–high;

a[low] = a[high];

while (low

www.9778.com,++low;

a[high] = a[low];

}//终止while循环之后low和high一定是相等的

a[low] = val;

return high; //high可以改为low, 但不能改为val 也不能改为a[low] 
也不能改为a[high]

}

void QuickSort(int *a,int low,int high)

{

int pos;

if(low

{

pos = FindPos(a,low,high);//找到a数组下标low-high 

QuickSort(a,low,pos-1);//把元素劈成两半  左半边

QuickSort(a,pos+1,high);//右半边

}

}

void main()

{

int i;

int a[6] = {2,1,3,0,5,4};

QuickSort(a,0,5);//0表示第一个元素下标 5表示最后一个元素的下标

for(i = 0;i<6;++i)

printf(“%dn”,a[i]);

}

4-插入排序

原理

依次选择一个待排序的数据,插入到前边已排好序的序列中。

性能

时间复杂度为O(N^2),空间复杂度为O(1)。算法是稳定的,比较次数和交换次数都与初始序列有关。

优化

直接插入排序每次往前插入时,是按顺序依次往前找,可在这里进行优化,往前找合适的插入位置时采用二分查找的方式,即折半插入。

折半插入排序相对直接插入排序而言:平均性能更快,时间复杂度降至O(NlogN),排序是稳定的,但排序的比较次数与初始序列无关,总是需要foor(log(i))+1次排序比较。

使用场景

当数据基本有序时,采用插入排序可以明显减少数据交换和数据移动次数,进而提升排序效率

代码:

void insert_sort(int *a,int n)

{

    int i,j,temp;

    for(i=1;i

    {

        temp=a[i]; /*temp为要插入的元素*/

        j=i-1;

        while(j>=0&&temp

        {

            /*从a[i-1]开始找比a[i]小的数,同时把数组元素向后移*/

            a[j+1]=a[j];

            j–;

        }

        a[j+1]=temp; /*插入*/

    }

}

5-希尔排序

原理

Shell法是一个叫 shell
的美国人与1969年发明的。它首先把相距k(k>=1)的那几个元素排好序,再缩小k值(一般取其一半),再排序,直到k=1时完成排序

插入排序的改进版,是基于插入排序的以下俩点性质而提出的改进方法:

插入排序对几乎已排好序的数据操作时,效率很高,可以达到线性排序的效率。

但插入排序在每次往前插入时只能将数据移动一位,效率比较低。

性能

开始时,gap取值较大,子序列中的元素较少,排序速度快,克服了直接插入排序的缺点;其次,gap值逐渐变小后,虽然子序列的元素逐渐变多,但大多元素已基本有序,所以继承了直接插入排序的优点,能以近线性的速度排好序。

void shell_sort(int *a,int n)

{

    int i,j,k,x;

    k=n/2; /*间距值*/

    while(k>=1)

    {

        for(i=k;i

        {

                x=a[i];

                j=i-k;

                while(j>=0&&x

                {

                    a[j+k]=a[j];

                    j-=k;

                }

                  a[j+k]=x;   

        }

                k/=2; /*缩小间距值*/

    }

}

6-归并排序

原理

分而治之思想:

Divide:将n个元素平均划分为各含n/2个元素的子序列;

Conquer:递归的解决俩个规模为n/2的子问题;

Combine:合并俩个已排序的子序列。

性能

时间复杂度总是为O(NlogN),空间复杂度也总为为O(N),算法与初始序列无关,排序是稳定的。

优化

优化思路:

在规模较小时,合并排序可采用直接插入;

在写法上,可以在生成辅助数组时,俩头小,中间大,这时不需要再在后边加俩个while循环进行判断,只需一次比完

//归并排序

void merge(int arr[],int temp_arr[],int left,int mid, int right){

    //简单归并:先复制到temp_arr,再进行归并

    for (int i = left; i <= right; i++){

        temp_arr[i] = arr[i];

    }

    int pa = left, pb = mid + 1;

    int index = left;

    while (pa <= mid && pb <= right){

        if (temp_arr[pa] <= temp_arr[pb]){

            arr[index++] = temp_arr[pa++];

        }

        else{

            arr[index++] = temp_arr[pb++];

        }

    }

    while(pa <= mid){

        arr[index++] = temp_arr[pa++];

    }

    while (pb <= right){

        arr[index++] = temp_arr[pb++];

    }

}

void merge_improve(int arr[], int temp_arr[], int left, int mid,
int right){

    //优化归并:复制时,俩头小,中间大,一次比较完

    for (int i = left; i <= mid; i++){

        temp_arr[i] = arr[i];

    }

    for (int i = mid + 1; i <= right; i++){

        temp_arr[i] = arr[right + mid + 1 – i];

    }

    int pa = left, pb = right, p = left;

    while (p <= right){

        if (temp_arr[pa] <= temp_arr[pb]){

            arr[p++] = temp_arr[pa++];

        }else{

            arr[p++] = temp_arr[pb–];

        }

    }

}

void merge_sort(int arr[],int temp_arr[], int left, int right){

    if (left < right){

        int mid = (left + right) / 2;

        merge_sort(arr,temp_arr,0, mid);

        merge_sort(arr, temp_arr,mid + 1, right);

        merge(arr,temp_arr,left,mid,right);

    }

}

void merge_sort(int arr[], int len){

    int *temp_arr = (int*)malloc(sizeof(int)*len);

    merge_sort(arr,temp_arr, 0, len – 1);

}

7-堆排序

原理

堆的性质:

是一棵完全二叉树

每个节点的值都大于或等于其子节点的值,为最大堆;反之为最小堆。

堆排序思想:

将待排序的序列构造成一个最大堆,此时序列的最大值为根节点

依次将根节点与待排序序列的最后一个元素交换

再维护从根节点到该元素的前一个节点为最大堆,如此往复,最终得到一个递增序列

性能

时间复杂度为O(NlogN),空间复杂度为O(1),因为利用的排序空间仍然是初始的序列,并未开辟新空间。算法是不稳定的,与初始序列无关。

使用场景

想知道最大值或最小值时,比如优先级队列,作业调度等场景。

代码

/**

    * 将数组arr构建大根堆

    * @param arr 待调整的数组

    * @param i  待调整的数组元素的下标

    * @param len 数组的长度

    */

    void heap_adjust(int arr[], int i, int len)

    {

        int child;

        int temp;

        for (; 2 * i + 1 < len; i = child)

        {

            child = 2 * i + 1;  // 子结点的位置 = 2 * 父结点的位置 + 1

            // 得到子结点中键值较大的结点

            if (child < len – 1 && arr[child + 1] >
arr[child])

                child ++;

            //
如果较大的子结点大于父结点那么把较大的子结点往上移动,替换它的父结点

            if (arr[i] < arr[child])

            {

                temp = arr[i];

                arr[i] = arr[child];

                arr[child] = temp;

            }

            else

                break;

        }

    }

    /**

    * 堆排序算法

    */

    void heap_sort(int arr[], int len)

    {

        int i;

        //
调整序列的前半部分元素,调整完之后第一个元素是序列的最大的元素

        for (int i = len / 2 – 1; i >= 0; i–)

        {

            heap_adjust(arr, i, len);

        }

        for (i = len – 1; i > 0; i–)

        {

            //
将第1个元素与当前最后一个元素交换,保证当前的最后一个位置的元素都是现在的这个序列中最大的

            int temp = arr[0];

            arr[0] = arr[i];

            arr[i] = temp;

            //
不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值

            heap_adjust(arr, 0, i);

        }

    }

相关链接:http://blog.poetries.top/2016/04/30/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93/