分類: 算法

排序算法-快速排序(三者取中劃分)

快速排序算法的一個改進版本,在數組取三個元素的中間進行劃分.這樣可以避免出現最壞的情況.

取數組的左邊,中間,右邊的元素.對這三個數進行排序.

#define less(A,B)     ((A)<(B)) // 小於比較

#define exch(A,B)     {int temp=A; A=B; B=temp;} // 交換

#define compexch(A,B) if(less(A,B)) exch(A,B) // 小於則交換

下面給出C代碼的實現.

// 劃分算法

//a:數組

//l:數組的左則索引

//r:數組的右則索引

void quicksort(int a[],int l,int r)

{

int i;

int temp;

// a[(l+r)/2] 與 a[r-1]交換

exch(a[(l+r)/2], a[r-1]);

// 取數組的左邊,中間,右邊的元素.對這三個數進行排序.

// 小於則交換

compexch(a[r-1],a[l]);

compexch(a[r],  a[l]);

compexch(a[r],  a[r-1]);

i = partition(a,l+1,r-1);

quicksort(a[],l,  i-1);

quicksort(a[],i+1,r);

}

// 劃分算法

//a:數組

//l:數組的左則索引

//r:數組的右則索引

int partition(int a[],int l,int r)

{

int i,j,v,t;

i = l;

j = r;

v = a[j];//選則最右則的元素作為劃分元素v

while(true)

{

while(a[i]<v)

++i;// i的左則小與v

while(v<a[j])

{

++j;// j的右則大與v

if(j==l)

break;// 跳出

}

if(i>=j)

break;// 兩個指針相遇跳出掃描.

// 交換i,j,交換那些使掃描停止的元素.

t=a[i];

a[i]=a[j];

a[j]=t;

}

// 交換i,r,保證v的左則小於於它,v的右則大於它.

t=a[i];

a[i]=a[r];

a[r]=t;

return i;

}

排序算法-快速排序(非递归)

1.选则最右则的元素作为划分元素v,然后从左则扫描小于v的元素,然后从右则扫描大于v的元素.
交换那些使扫描停止的元素.
2.重复进行这样的过程直到两个指针相遇.
3.然后分别对左右两步分进行递归处理.最终得到一个排好序的数组.

// 全局数据
int stack[128];// 堆栈
int ps;// 堆栈指针
//初始化堆栈
void init()
{
ps = 0;
}

//堆栈是否为空
int IsEmpty()
{
if(ps == 0)
return 1;
else
return 0;
}

// 压入
void push(int v)
{
stack[ps]=v;
++ps;// 指针加一
}

// 弹出
int pop()
{
if(ps == 0)
return = 0;
–ps;// 指针减一
return stack[ps];
}

下面给出C代码的实现.
//快速排序(非递归)
//a:数组
//l:数组的左则索引
//r:数组的右则索引
void quicksort(int a[],int l,int r)
{
init();
push(l);
push(r);

while(IsEmpty())
{
l=pop();
r=pop();
if(r<=l)
continue;
i=partition(a,l,r);
if(i-l < r-i)
{
push(l);
push(i-1);

push(i+1);
push(r);
}
else
{
push(i+1);
push(r);

push(l);
push(i-1);
}
}

}

// 划分算法
//a:数组
//l:数组的左则索引
//r:数组的右则索引
int partition(int a[],int l,int r)
{
int i,j,v,t;
i = l;
j = r;
v = a[j];//选则最右则的元素作为划分元素v
while(true)
{
while(a[i]<v)
++i;// i的左则小与v

while(v<a[j])
{
++j;// j的右则大与v
if(j==l)
break;// 跳出
}

if(i>=j)
break;// 两个指针相遇跳出扫描.

// 交换i,j,交换那些使扫描停止的元素.
t=a[i];
a[i]=a[j];
a[j]=t;
}

// 交换i,r,保证v的左则小于于它,v的右则大于它.
t=a[i];
a[i]=a[r];
a[r]=t;

return i;
}

排序算法-快速排序
快速排序是由C.A.R.Hoare在1960年提出.对于大型数据,快速排序算法的性能是希尔排序的5到10倍.
快速排序是一种分而治之算法,它将素组划分成两部分,然后分别对两个部分进行排序.
1.选则最右则的元素作为划分元素v,然后从左则扫描小于v的元素,然后从右则扫描大于v的元素.
交换那些使扫描停止的元素.
2.重复进行这样的过程直到两个指针相遇.
3.然后分别对左右两步分进行递归处理.最终得到一个排好序的数组.

下面给出C代码的实现.
// 划分算法
//a:数组
//l:数组的左则索引
//r:数组的右则索引
int   partition(int a[],int l,int r)
{
int i,j,v,t;
i = l;
j = r;
v = a[j];//选则最右则的元素作为划分元素v
while(true)
{
while(a[i]<v)
++i;// i的左则小与v

while(v<a[j])
{
++j;// j的右则大与v
if(j==l)
break;// 跳出
}

if(i>=j)
break;// 两个指针相遇跳出扫描.

// 交换i,j,交换那些使扫描停止的元素.
t=a[i];
a[i]=a[j];
a[j]=t;
}

// 交换i,r,保证v的左则小于于它,v的右则大于它.
t=a[i];
a[i]=a[r];
a[r]=t;

return i;
}

//快速排序
//a:数组
//l:数组的左则索引
//r:数组的右则索引
void quicksort(int a[],int l,int r)
{
int i;
if(l<=0)
return ;
quicksort(a,l,  i-1);
quicksort(a,i+1,r);
}

//快速排序
//a:数组
//c:数组的长度
void quicksort(int a[],int c)
{
quicksort(a,0,c-1);
}

 

排序算法-希尔排序
1.希尔排序是查入排序的扩展版.在扫描数据时,把移动的增量或减量由原来的1变成h.
2.h就是步长.对于每个h,对每个h单独使用插入排斥.

下面给出C代码的实现.
//a:数组
//l:数组的长度
void shellsort(int a[],int l)
{
int i,j;
int h;// 步长
int v;

// 计算步长
h=1;
while(h<=l/9)
h=3*h+1;

for(;h>0; h/=3)// 改边步长
{
for(i=h; i<=l; ++i)// 使用插入排斥
{
j=i;
v=a[i];
while(j>=h && v < a[j-h])
{
a[j]=a[j-h];
j-=h;
a[j]=v;
}
}
}
}

排序算法-冒泡排序
1.进行遍历,当遇到最小元素时,将它与左边的元素逐个交换.直到将最小的元素移到对列的最左边.
2.进行遍历,将第二小的元素放到数组的左边第二个元素中.
3.以此类推.
冒泡排序,实际是选择排序,但需要更多CPU开销.
冒泡排序排序的特点是容易实现,不过比插入排序和选择排序慢.

下面给出C代码的实现.
//a:数组
//l:数组的长度
void bubble(int a[],int l)
{
int i,j;// 索引
int temp;// 用于交换
for(i=0;i<l;++i)
{
for(j=0;j<i;–j)
{   // 小于比较
if(a[j-1]<a[j])
{// 进行交换
temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
}
}
}

1.将最小的元素放在最前.将最小元素作为关键字.
2.索引的左则是以排好序的,但不是处于最终位置.当碰到更小的数据向右移动腾出空间,插入较小的数据.
3.索引加一并重复上叙步骤.
3.当索引移到最右则时,则数组拍好序.
和选择排序不同的是,插入排序的运行时间和数据的原始排列顺序密切相关.
如果数据量比较大,而且已经排好序或几乎排好序,插入排序比选则排序好.

下面给出C代码的实现.
//a:数组
//l:数组的长度
void insertion(int a[],int l)
{
int i,j;// 索引
int temp;// 用于交换
int v;
// 将最小的元素放在最前.
for(i = l-1; i>0; –i)
{
// 进行小于比较
if(a[i-1] < a[i])
{// 交换
temp = a[i-1];
a[i-1] = a[i];
a[i] = temp;
}
}

for(i=2; i < l; ++i)
{
j = i;
v = a[i];
// 小于比较
while(v < a[j-1])
{// 向右移
a[j] = a[j-1];
j–;
a[j] = v;
}
}

}

排序算法之选择排序
它是一种最简单的排序算法,
1.选出数组中最小的元素,将它与数组中地一个元素交换.
2.然后找出次小元素,将它与数组中第二个元素进行交换.
3.重复这个方法,直到整个数组排序完毕.
选择排序的一个缺点是忽略有序部分.
当数组比较大,数据又比较小.则应选择改方法.
它与其它比算法相比,移动步数都要比选择排序要多.

下面给出C代码的实现.
//a:数组
//l:数组的长度
void selection(int a[],int l)
{
int i,j;//排序索引
for(i = 0; i < l; ++i)
{
int min = i;
for( j = i+1; j < l; ++j)
{   // 进行小于比较
if(a[j] < a[min])
min = j;
}
// 进行交换
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}