【编程珠玑】第十一章 排序 （插入排序和快速排序的深度优化）

一，概述

1）插入排序

要找到合适的位置，需要判断前一个元素比t小而后一个元素比t大。然后将t插入正确位置。

比较a[j-1] 跟 a[j] 的关系很关键

isort1: 没有到达最终位置，就交换该元素和它前面的元素

#include <algorithm>

        for(int i=1;i<5;i++)
		for(int j=i;j>0&&a[j-1]>a[j];j--)	   	    	   		
   	   			  swap(a[j-1],a[j]);

  isort2:将库函数替换

	int temp;
	for(int i=1;i<5;i++)	
		for(int j=i; j>0 && a[j-1]>a[j]; j--)
		   {
   	   			  temp=a[j];
   	   			  a[j]=a[j-1];
   	   			  a[j-1]=temp;			
   	    	}

isort3:减少移动次数

	for(i=1;i<5;i++)
	{
		t=a[i];
		for(j=i; j>0 && a[j-1]>t; j--)
   	   			  a[j]=a[j-1];    	   			  
        a[j]=t; 	   			    	
	}

2）快速排序

  qsort1:O(nlog(n)时间和O(logn)的栈空间

#include"stdio.h"
void  Partition(int a[],int left,int right)
{
	int i=left,j=right;
	int temp=a[i];//记录下轴的位置 
	
	if(left>=right)//退出条件
		return;
	
	while(i<j)
	{
		while(i<j&&temp<=a[j])//从右侧查找，找到第一个比轴小的 
		   j--;
     
                a[i]=a[j];//小的 等于后面的大的 (之后的i 会增加)【后面的大的 移动到前面来后 本趟不会再动】 
       
          
                while(i<j&&temp>=a[i])//从左侧查找，找到第一个比轴大的  
                       i++;
        
                a[j]=a[i]; // 大的后移
        
 	  
	}
	a[i]=temp;//找到轴的正确位置
	
	Partition(a,left,j-1);
	Partition(a,j+1,right);		
}
int main()
{
	int a[10]={3,4,2,1,6,5,7,8};	
	Partition(a,0,7);	
	for(int i=0;i<8;i++)
            printf("%d\n",a[i]);
      
	return 0;
}

qsort2:双向划分避免所有元素都相等时候的最坏情况

#include <iostream>
#include <algorithm>
using namespace std;
void quictSort(int a[],int l,int u)
{
	if(l >= u)
		return;
	int t = a[l];//记录轴
	int i = l;
	int j = u+1;
	for(;;)
	{
		do i++;while(i <= u && a[i] < t);//先i++再判断条件
		do j--;while(a[j] > t);          //先j--再判断条件
		if(i > j) //无限循环退出的条件
			break;
		swap(a[i],a[j]);//每找到一个前面元素大于等于轴，跟后面小于等于轴的就交换
	}
	swap(a[l],a[j]);
	quictSort(a,l,j-1);
	quictSort(a,j+1,u);
}
int main()
{	
	int a[10]={3,4,2,1,6,5,7,8};	
	quictSort(a,0,7);	
	for(int i=0;i<8;i++)
            printf("%d\n",a[i]);
	return 0;
}

思路：n个相同元素组成的数组，插入排序性能最好（每个元素需要移动的距离都为0）,时间复杂度为o(n)。 快速排序的性能则很糟糕，n-1次划分每次划分都需要0(n)的时间来去掉一个元素，所以时间复杂度为O(n*n) 采取的对策是：采取两个内循环，第一个向右移过小元素，遇到大元素停止，第二个左移，遇到小元素停止。然后交换。 当遇到相同的元素时，停止扫描，交换a[i] 和 a[j]的值。最坏时间复杂度O(nlogn)

 qsort3:利用随机位置的数做轴，会使数组的快速排序得到优化。

#include <iostream>
#include <algorithm>
using namespace std;
void quictSort(int a[],int l,int u)
{
	if(l >= u)
		return;
	swap(a[l],a[rand()%(u-l) + l]);//仅仅是在这里做文章
	
	int t = a[l];
	int i = l;
	int j = u+1;
	for(;;)
	{
		do i++;while(i <= u && a[i] < t);
		do j--;while(a[j] > t);
		if(i > j)
			break;
		swap(a[i],a[j]);
	}
	swap(a[l],a[j]);
	quictSort(a,l,j-1);
	quictSort(a,j+1,u);
}
int main()
{	
	int a[10]={3,4,2,1,6,5,7,8};	
	quictSort(a,0,7);	
	for(int i=0;i<8;i++)
      printf("%d\n",a[i]);
	return 0;
}

<pre></pre>

【知识点】产生某个范围随机数方法：

  比如要产生 [60-99]的随机数.

  使用rand()函数产生的随机数是从0(包括0)开始的
  我们思考:

  [ 0,?] + 60 =[60,99]
  很明显,?应该是39.产生[0, 39]的随机数可以这样做:rand() % 40 得解.

#include <iostream>
using namespace std;
#include <cstdlib>
#include <ctime>


int main()
{
 srand(time(NULL));//种子不同生产的随机数不同


 for (int i=0; i!=50; ++i)
 {
  cout << rand() % 40 + 60 << endl;
 }
}

rand()%(end-start)+start;

注意：因为rand()函数是按指定的顺序来产生整数，因此每次执行上面的语句都打印相同的值，所以说C语言的随机并不是真正意义上的随机，有时候也叫伪随机数

二，习题

     2）Lomuto的快速排序算法如下

<span style="font-size: 18px;">#include <iostream>
#include <algorithm>
using namespace std;
void quictSort(int a[],int l,int u)
{
	if(l >= u)
		return;
	int m = l;//记录轴
	
	for(int i=l+1;i<=u;++i)
	{
		if(a[i] < a[l]) //小于轴 
			swap(a[++m],a[i]);//换到前面来  ++m说明轴的位置向后移动 	
	}
	swap(a[l],a[m]); //找到轴的位置，交换 
	quictSort(a,l,m-1);
	quictSort(a,m+1,u);
}
int main()
{	
	int a[10]={3,4,2,1,6,5,7,8};	
	quictSort(a,0,7);	
	for(int i=0;i<8;i++)
            printf("%d\n",a[i]);
	return 0;
}</span>

      采用哨兵优化后算法:（减少了内循环测试）

<span style="font-size: 18px;">#include <iostream>
#include <algorithm>
using namespace std;
void quictSort(int a[],int l,int u)
{
	if(l >= u)
		return;
	int m = u+1;//记录轴
    int i=  u+1;
	do{
		while(a[--i]<a[l]);//找到比轴大的 a[i]
		 
		swap(a[--m],a[i]);//将比轴大的交换到后面 m-- m是计算的比轴大的元素然后左移
	}while(i!=l);
			
	
	
	quictSort(a,l,m-1);
	quictSort(a,m+1,u);
}
int main()
{	
	int a[10]={3,4,2,1,6,5,7,8};	
	quictSort(a,0,7);	
	for(int i=0;i<8;i++)
            printf("%d\n",a[i]);
	return 0;
}</span>

      
        5）没完全理解题意

        6）选择排序

<span style="font-size: 18px;">#include <iostream>
#include <algorithm>
using namespace std;
void selectSort(int a[],int n)
{
	for(int i=0;i<n;++i)
	{
		for(int j=i;j<n;++j)
		{
			if(a[i]>a[j])
				swap(a[i],a[j]);
		}
	}
}
int main()
{	
	int a[10]={3,4,2,1,6,5,7,8};	
	selectSort(a,7);	
	for(int i=0;i<8;i++)
            printf("%d\n",a[i]);
	return 0;
}</span>

          希尔排序：选择排序的优化

<span style="font-size: 18px;">#include"stdio.h"

void shellsort(int a[],int n)
{
	int k=n/2;//第一个间距  分成两个一组 
	while(k>0)
	{
		for(int i=k;i<n;i++)//从与第一个值间距 n/2开始比较 
		{
			int t=a[i];//与第一个值间距 n/2的值 
			int j=i-k;//第一趟 i=k 取的第一个数 
			while(j>=0&&t<a[j])//后面的数是不是小 ？ 
			{
				a[j+k]=a[j];
				j=j-k; //如果互换了  这里将变成负的 
			}
			a[j+k]=t;
		}
		
		
		k=k/2; 
	}
	
}
int main()
{
	int a[9]={2,1,3,6,5,4,8,7};	
	shellsort(a,8);
	
	for(int i=0;i<8;i++)
	   printf("%d\n",a[i]); 
	return 0;
} </span>

        9）线性时间寻找第k小元素

          思路：快速排序选择一个pivot对数组进行划分，左边小于pivot，右边大于等于pivot，所以我们计算左边小于pivot(加上pivot)的个数count总共有多少，如果等于k,正是我们所要的，如果大于k，说明第k小的数在左边，那就在左边进行我们的递归；否则，在右边，那么说明右边的第k-count小的数就是我们所要的，在右边进行我们的递归。

          算法实现一：

#include<iostream>
using namespace std;

inline void Swap(int a[],int i,int j)//内联函数，交换两个元素位置
{
    int temp=a[i];
    a[i]=a[j];
    a[j]=temp;
}

int Partition(int a[],int p,int r)//根据pivot a[r]来划分数组
{
    int pivot=a[r];
    int low=p-1;
    int i;
    for(i=p;i<r;i++)
    {
        if(a[i]<=pivot)
            Swap(a,++low,i);
    }
    Swap(a,++low,r);
    return low;
}

int RondomPartition(int a[],int p,int r)
{
    int i=p+rand()%(r-p+1);//随机选择一个pivot来划分
     Swap(a,i,r);
    return Partition(a,p,r);//返回轴位置
}

int SelectKMin(int a[],int p,int r,int k)
{
    if(p==r)
        return a[p];
    int q=RondomPartition(a,p,r);
    int count=q-p+1;//计算 a[p..q]的元素数量 
    if(k==count)//刚好,返回
        return a[q];
    else if(k<count)//在前半部分
        return SelectKMin(a,p,q-1,k);
    else //在后半部分
        return SelectKMin(a,q+1,r,k-count);
}

int main()
{
    int a[]={2,3,4,1,5,10,9,7,8,6};
	int k=3;
    cout<<SelectKMin(a,0,9,k)<<endl;
    
    return 0;
}

算法实现二：

#include"stdio.h"
int GetMinK(int A[],int n,int k)
{
	int s=-1,i=0,j=n-1,temp;
	int beg=i;
	int end=j;
	while(s!=k)
	{
  		beg=i;
  		end=j;
  		temp=A[i];
  		while(i<j)
  		{
   			while(i<j&&A[j]>=temp)j--;A[i]=A[j];
                   while(i<j&&A[i]<=temp)i++;A[j]=A[i];
 		}
 		 A[i]=temp;
 	 	s=i;
 
   
  		if(s==k)
		  	return A[k];
  		if(s>k){i=beg;j--;} //在左侧寻找 
  		if(s<k){j=end;i++;} //在右侧寻找 
	}
}
int main()
{
	int A[]={2,3,4,1,5,10,9,7,8,6};
	int k=3;
	printf("第%d小元素为：(从0开始)\n%d ",k,GetMinK(A,10,k));
	return 0;
}

14）算法实现如下：

#include <iostream>
#include <algorithm>
using namespace std;
void quictSort(int a[],int u)
{
	if(u<=1)
		return;
	int m = 0;//记录轴
	
	for(int i=1;i<=u;++i)
	{
		if(a[i] < a[0]) //小于轴 
			swap(a[++m],a[i]);//换到前面来  ++m说明轴的位置向后移动 	
	}
	swap(a[0],a[m]); //找到轴的位置，交换 
	
	quictSort(a,m-1);
	quictSort(a+m+1,u-m-1);
}
int main()
{	
	int a[10]={3,4,2,1,6,5,7,8};	
	quictSort(a,7);	
	for(int i=0;i<8;i++)
            printf("%d\n",a[i]);
	return 0;
}