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

一，概述
        1）插入排序
         要找到合适的位置，需要判断前一个元素比t小而后一个元素比t大。然后将t插入正确位置。
         比较a[j-1] 跟 a[j] 的关系很关键

         isort1: 没有到达最终位置，就交换该元素和它前面的元素
#include <algorithm>
[html]
for(int i=1;i<5;i++)
t j=i;j>0&&a[j-1]>a[j];j--)
          swap(a[j-1],a[j]);
     isort2:将库函数替换

[html]
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:减少移动次数

[html]
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)的栈空间

[html]
#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:双向划分避免所有元素都相等时候的最坏情况

[html]
#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:利用随机位置的数做轴，会使数组的快速排序得到优化。

[html]
#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;
  &nb

补充：软件开发 , 其他 ,