T9的空间

You will never walk alone!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  69 随笔 :: 0 文章 :: 28 评论 :: 0 Trackbacks
一种说法,对极了---我觉得
快速排序和归并排序其实是一种想法,都是用的分治的思路,只是分的key不同,快排是根据排序元素的值来分,分成比关键字大的,比关键字小的,确定自己的位子;而归并是按序号(位置)来分,通常用的是二分,从中间均匀分开,使分治后的子问题达到一种平衡,降低复杂度。而快排在选取关键字的时候一般用开头第一个元素,随机的,没有更好的办法可以使分治后的子问题达到一种平衡。

#include
<iostream>
#include
<algorithm>
#include
<cmath>
using namespace std;

#define N 100
int array[N];

int partition(int a[],int s,int e)//分治
{
    
int i=s,j=e;
    
while(i<j)
    
{
        
while(i<j&&a[j]>a[i]) j--;
        
if(i<j)
        
{
            swap(a[j],a[i]);
            i
++;
        }

        
while(i<j&&a[i]<a[j]) i++;
        
if(i<j)
        
{
            swap(a[i],a[j]);
            j
--;
        }

    }

    
return i;
}


void qsort(int a[],int s,int e)
{
    
if(s<e)
    
{
        
int mid=partition(a,s,e);
        
//cout<<mid<<endl;
        qsort(a,s,mid-1);
        qsort(a,mid
+1,e);
    }

}


int main()
{
    
int i;
    
for(i=0;i<20;i++)
        array[i]
=rand()%100;
    qsort(array,
0,19);
    
for(i=0;i<20;i++)
        printf(
"%d ",array[i]);
    printf(
"\n");
    
return 0;
}


在写这个代码的时候出了个问题,在左右扫描数组的时候,没有在交换以后改变指针i,j的值,而认为在while中循环是改变是一样的,但这会在某种情况下导致死循环。

0 5 24 27 27 34 36 41 42 45 58 61 62 64 67 69 78 81 91 95
Press any key to continue

 

posted on 2008-11-23 15:06 Torres 阅读(197) 评论(0)  编辑 收藏 引用 所属分类: Data Structures

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理