`

经典排序算法-C实现

 
阅读更多

转载自:http://blog.csdn.net/subo86/article/details/3847016

经典排序算法-C实现

PART (1)

/*
===============================================
经典排序思想,并用C语言指针实现排序算法
================================================
*/

/*
=============================================================================
相关知识介绍(所有定义只为帮助读者理解相关概念,并非严格定义):
1、稳定排序和非稳定排序

简单地说就是所有相等的数经过某种排序方法后,仍能保持它们在排序之前的相对次序,我们就
说这种排序方法是稳定的。反之,就是非稳定的。
比如:一组数排序前是a1,a2,a3,a4,a5,其中a2=a4,经过某种排序后为a1,a2,a4,a3,a5,
则我们说这种排序是稳定的,因为a2排序前在a4的前面,排序后它还是在a4的前面。假如变成a1,a4,
a2,a3,a5就不是稳定的了。

2、内排序和外排序

在排序过程中,所有需要排序的数都在内存,并在内存中调整它们的存储顺序,称为内排序;
在排序过程中,只有部分数被调入内存,并借助内存调整数在外存中的存放顺序排序方法称为外排序。

3、算法的时间复杂度和空间复杂度

所谓算法的时间复杂度,是指执行算法所需要的计算工作量。
一个算法的空间复杂度,一般是指执行这个算法所需要的内存空间。
================================================================================
*/


/*
================================================
功能:选择排序
输入:数组名称(也就是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述:

在要排序的一组数中,选出最小的一个数与第一个位置的数交换;
然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环
到倒数第二个数和最后一个数比较为止。

选择排序是不稳定的。算法复杂度O(n2)--[n的平方]
=====================================================
*/
void select_sort(int *x, int n)
{
int i, j, min, t;

for (i=0; i<n-1; i++)/*要选择的次数:0~n-2共n-1次*/
{
min = i;/*假设当前下标为i的数最小,比较后再调整*/
for (j=i+1; j<n; j++)/*循环找出最小的数的下标是哪个*/
{
if (*(x+j) < *(x+min))
{
min = j;/*如果后面的数比前面的小,则记下它的下标*/
}
}

if (min != i)/*如果min在循环中改变了,就需要交换数据*/
{
t = *(x+i);
*(x+i) = *(x+min);
*(x+min) = t;
}
}
}


/*
================================================
功能:直接插入排序
输入:数组名称(也就是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述:

在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排
好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数
也是排好顺序的。如此反复循环,直到全部排好顺序。

直接插入排序是稳定的。算法时间复杂度O(n2)--[n的平方]
=====================================================
*/
void insert_sort(int *x, int n)
{
int i, j, t;

for (i=1; i<n; i++)/*要选择的次数:1~n-1共n-1次*/
{
/*
暂存下标为i的数。注意:下标从1开始,原因就是开始时
第一个数即下标为0的数,前面没有任何数,单单一个,认为
它是排好顺序的。
*/
t=*(x+i);
for (j=i-1; j>=0 && t<*(x+j); j--)/*注意:j=i-1,j--,这里就是下标为i的数,在它前面有序列中找插入位置。*/
{
*(x+j+1) = *(x+j);/*如果满足条件就往后挪。最坏的情况就是t比下标为0的数都小,它要放在最前面,j==-1,退出循环*/
}

*(x+j+1) = t;/*找到下标为i的数的放置位置*/
}
}


/*
================================================
功能:冒泡排序
输入:数组名称(也就是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述:

在要排序的一组数中,对当前还未排好序的范围内的全部数,自上
而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较
小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要
求相反时,就将它们互换。

下面是一种改进的冒泡算法,它记录了每一遍扫描后最后下沉数的
位置k,这样可以减少外层循环扫描的次数。

冒泡排序是稳定的。算法时间复杂度O(n2)--[n的平方]
=====================================================
*/

void bubble_sort(int *x, int n)
{
int j, k, h, t;

for (h=n-1; h>0; h=k)/*循环到没有比较范围*/
{
for (j=0, k=0; j<h; j++)/*每次预置k=0,循环扫描后更新k*/
{
if (*(x+j) > *(x+j+1))/*大的放在后面,小的放到前面*/
{
t = *(x+j);
*(x+j) = *(x+j+1);
*(x+j+1) = t;/*完成交换*/
k = j;/*保存最后下沉的位置。这样k后面的都是排序排好了的。*/
}
}
}
}


/*
================================================
功能:希尔排序
输入:数组名称(也就是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述:

在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,
并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为
增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除
多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现
了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中
记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量
对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成
一组,排序完成。

下面的函数是一个希尔排序算法的一个实现,初次取序列的一半为增量,
以后每次减半,直到增量为1。

希尔排序是不稳定的。
=====================================================
*/
void shell_sort(int *x, int n)
{
int h, j, k, t;

for (h=n/2; h>0; h=h/2)/*控制增量*/
{
for (j=h; j<n; j++)/*这个实际上就是上面的直接插入排序*/
{
t = *(x+j);
for (k=j-h; (k>=0 && t<*(x+k)); k-=h)
{
*(x+k+h) = *(x+k);
}
*(x+k+h) = t;
}
}
}


/*
================================================
功能:快速排序
输入:数组名称(也就是数组首地址)、数组中起止元素的下标
================================================
*/
/*
====================================================
算法思想简单描述:

快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟
扫描后,使得排序序列的长度能大幅度地减少。在冒泡排序中,一次
扫描只能确保最大数值的数移到正确位置,而待排序序列的长度可能只
减少1。快速排序通过一趟扫描,就能确保某个数(以它为基准点吧)
的左边各数都比它小,右边各数都比它大。然后又用同样的方法处理
它左右两边的数,直到基准点的左右只有一个元素为止。它是由
C.A.R.Hoare于1962年提出的。

显然快速排序可以用递归实现,当然也可以用栈化解递归实现。下面的
函数是用递归实现的,有兴趣的朋友可以改成非递归的。

快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n),最坏O(n2)

=====================================================
*/
void quick_sort(int *x, int low, int high)
{
int i, j, t;

if (low < high)/*要排序的元素起止下标,保证小的放在左边,大的放在右边。这里以下标为low的元素为基准点*/
{
i = low;
j = high;
t = *(x+low);/*暂存基准点的数*/

while (i<j)/*循环扫描*/
{
while (i<j && *(x+j)>t)/*在右边的只要比基准点大仍放在右边*/
{
j--;/*前移一个位置*/
}

if (i<j)
{
*(x+i) = *(x+j);/*上面的循环退出:即出现比基准点小的数,替换基准点的数*/
i++;/*后移一个位置,并以此为基准点*/
}

while (i<j && *(x+i)<=t)/*在左边的只要小于等于基准点仍放在左边*/
{
i++;/*后移一个位置*/
}

if (i<j)
{
*(x+j) = *(x+i);/*上面的循环退出:即出现比基准点大的数,放到右边*/
j--;/*前移一个位置*/
}
}

*(x+i) = t;/*一遍扫描完后,放到适当位置*/
quick_sort(x,low,i-1);/*对基准点左边的数再执行快速排序*/
quick_sort(x,i+1,high);/*对基准点右边的数再执行快速排序*/
}
}


/*
================================================
功能:堆排序
输入:数组名称(也就是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述:

堆排序是一种树形选择排序,是对直接选择排序的有效改进。
堆的定义如下:具有n个元素的序列(h1,h2,...,hn),当且仅当
满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)
时称之为堆。在这里只讨论满足前者条件的堆。

由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项。完全二叉树可以
很直观地表示堆的结构。堆顶为根,其它为左子树、右子树。
初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的存储顺序,
使之成为一个堆,这时堆的根节点的数最大。然后将根节点与堆的最后一个节点
交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推,直到只有两个节点
的堆,并对它们作交换,最后得到有n个节点的有序序列。

从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素
交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数
实现排序的函数。

堆排序是不稳定的。算法时间复杂度O(nlog2n)。

*/
/*
功能:渗透建堆
输入:数组名称(也就是数组首地址)、参与建堆元素的个数、从第几个元素开始
*/
void sift(int *x, int n, int s)
{
int t, k, j;

t = *(x+s);/*暂存开始元素*/
k = s;/*开始元素下标*/
j = 2*k + 1;/*右子树元素下标*/

while (j<n)
{
if (j<n-1 && *(x+j) < *(x+j+1))/*判断是否满足堆的条件:满足就继续下一轮比较,否则调整。*/
{
j++;
}

if (t<*(x+j))/*调整*/
{
*(x+k) = *(x+j);
k = j;/*调整后,开始元素也随之调整*/
j = 2*k + 1;
}
else/*没有需要调整了,已经是个堆了,退出循环。*/
{
break;
}
}

*(x+k) = t;/*开始元素放到它正确位置*/
}


/*
功能:堆排序
输入:数组名称(也就是数组首地址)、数组中元素个数
*/
void heap_sort(int *x, int n)
{
int i, k, t;
int *p;

for (i=n/2-1; i>=0; i--)
{
sift(x,n,i);/*初始建堆*/
}

for (k=n-1; k>=1; k--)
{
t = *(x+0);/*堆顶放到最后*/
*(x+0) = *(x+k);
*(x+k) = t;
sift(x,k,0);/*剩下的数再建堆*/
}
}


void main()
{
#define MAX 4
int *p, i, a[MAX];

/*录入测试数据*/
p = a;
printf("Input %d number for sorting :/n",MAX);
for (i=0; i<MAX; i++)
{
scanf("%d",p++);
}
printf("/n");

/*测试选择排序*/


p = a;
select_sort(p,MAX);
/**/


/*测试直接插入排序*/

/*
p = a;
insert_sort(p,MAX);
*/


/*测试冒泡排序*/

/*
p = a;
insert_sort(p,MAX);
*/

/*测试快速排序*/

/*
p = a;
quick_sort(p,0,MAX-1);
*/

/*测试堆排序*/

/*
p = a;
heap_sort(p,MAX);
*/

for (p=a, i=0; i<MAX; i++)
{
printf("%d ",*p++);
}

printf("/n");
system("pause");
}

PART(2)

常用算法(插入,合并,快速,冒泡,堆,shell) C语言实现

#include<stdio.h>
#include<stdlib.h>
void BubbleSort(int a[], const int first, const int last);//冒泡排序
void InsertSort(int a[], const int first, const int last);//插入排序
void SelectSort(int a[], const int first, const int last);//选择排序
void MergeSort(int a[], const int p, const int r);//合并排序
void QuickSort(int a[],const int p,const int r);//快速排序
void ShellSort(int a[],const int p,const int r,const int dlta[],const int t);//希尔排序
void HeapSort(int a[],const int p, int r); //堆排序
void StoogeSort(int a[],const int p,const int r);//Stooge排序(不用)算法复杂度没算清楚

void main()
{
//插入排序算法
int a[11] = {6,4,5,3,2,1};
int dlta[]={9,5,3,2,1};
//BubbleSort(a,0,5);
//InsertSort(a,0,5);
//SelectSort(a,0,5);
//MergeSort(a,0,5);
//QuickSort(a,0,5);
//ShellSort(a,0,5,dlta,5);
HeapSort(a,0,5);
//StoogeSort(a,0,5);


for(int i=0; i<=5;i++)
{
printf("%d ",a[i]);
}

}

/************************冒泡排序***********************/
void BubbleSort(int a[], int first, int last)
{
//实现对数组a[]中a[first]到a[last]升序的“冒泡”排序
int i,j,temp;
for(i=first; i<=last; i++)
{
for(j=first; j< last-i; j++)
{
if(a[j] > a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}

/************************插入排序***********************/
void InsertSort(int a[], int first, int last)
{
//实现对数组a[]中a[first]到a[last]升序的“插入”排序
//最坏情况为n的平方,,多用于小数组
int i,j,temp;
for(i=first+1; i<=last; i++)
{
temp = a[i];
j = i - 1;
while((j >= 0) && (a[j] > temp))
{
a[j+1] = a[j];
j--;
}
a[j+1] = temp;
}
}

/************************选择排序***********************/
void SelectSort(int a[], int first, int last)
{
//实现对数组a[]中a[first]到a[last]升序的“选择”排序
int i, j, temp, num;
for(i=first; i<last; i++)
{
num = i;
for(j=i+1; j<=last; j++)
{
if(a[j] < a[num])
{
num = j;
}
}
if(i != num)
{
temp = a[num];
a[num] = a[i];
a[i] = temp;
}
}
}

/************************合并排序***********************/
void Merge(int a[],const int p,const int q,const int r)
{
//合并排序算法中的实现合并的子程序
int iLLength,iRLength;
int *L, *R, i, j, k;
iLLength = q - p + 1;
iRLength = r - q;
L = (int *)malloc(iLLength*sizeof(int)); //或者 C++中 new int[iLLength];
R = (int *)malloc(iRLength*sizeof(int)); //或者 C++中 new int[iRLength];
if(L == 0 || R== 0)
{
printf("内存分配失败!!!");
return;
}
for(i=0; i<iLLength; i++)
{
L[i] = a[p+i];
}
for(j=0; j<iRLength; j++)
{
R[j] = a[q+j+1];
}
i = 0;
j = 0;
for(k=p; k<=r; k++)
{
if((i<iLLength) && (j<iRLength) && (L[i]<=R[j]) || (j == iRLength))
{
a[k] = L[i];
i++;
}
else if(j<iRLength)
{
a[k] = R[j];
j++;
}
}

free(R);free(L);
}
void MergeSort(int a[],const int p,const int r)
{
//合并排序算法-主程序
//n*lg(n),系数较小
int q;
if(p<r)
{
q = (p+r)/2;
MergeSort(a,p,q);
MergeSort(a,q+1,r);
Merge(a,p,q,r);
}
}

/************************Stooge排序***********************/
void StoogeSort(int a[],const int p,const int r)
{
//Stooge算法
int temp, k;
if(a[p]>a[r])
{
temp = a[p];
a[p] = a[r];
a[r] = temp;
}
if((p+1) >= r)
{
return;
}
k = (r-p+1)/3;
StoogeSort(a,p,r-k);
StoogeSort(a,p+k,r);
StoogeSort(a,p,r-k);
}

/************************快速排序*********************/
int QuickPartition(int a[],const int p,const int r)
{
//快速排序的(关键)分治过程
int temp, x, i, j;
x = a[r];
i = p - 1;
for(j=p; j<r; j++)
{
if(a[j] <= x)
{
i = i + 1;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
temp = a[i+1];
a[i+1] = a[r];
a[r] = temp;
return (i+1);
}
/*
void QuickSort(int a[],const int p,const int r)
{
//快速排序算法-主程序
//与下面的“尾递归实现方法”比较,缺点:右边数组的递归不是必须的,增加了运行堆栈深度和调用开销
int q;
if(p < r)
{
q = QuickPartition(a, p, r);
QuickSort(a, p, q-1);
QuickSort(a, q+1, r);
}
}
*/
void QuickSort(int a[],int p,const int r)
{
//快速排序算法-主程序
//“尾递归实现方法”是对上面的快速排序主程序实现的一种优化
//系数较小,常用大数组
int q;
while(p < r)
{
q = QuickPartition(a, p, r);
QuickSort(a, p, q-1);
p = q + 1;
}
}

/************************希尔排序**********************/
void ShellInsert(int a[],const int p,const int r, int dk)
{
//希尔排序算法的关键子程序-插入排序子程序
int i, j, temp;
for(i=p+dk; i<=r; i++)
{
if(a[i] < a[i-dk])
{
temp = a[i];
for(j=i-dk; ((j>=0) && (temp < a[j])); j -= dk)
{
a[j+dk] = a[j];
}
a[j+dk] = temp;
}
}
}

void ShellSort(int a[],const int p,const int r,const int dlta[],const int t)
{
//希尔排序算法-主程序
//按增量序列dlta[]中的前t个增量,实现对数组a[]中a[p]到a[r]的排序
//dlta[]可能取值如:1,2,3,5,9 dala[k]=2^(t-k+1)-1 其中0<=k<=t<=ld(b-1)
//增量序列的最后一个值必须是1
//增量序列中的值没有除1以外的因子, 其精确时间复杂度:数学上尚未解决的难题
int k;
for(k=0; k<t; k++)
{
ShellInsert(a,p,r,dlta[k]);
}
}

/************************堆排序***********************/
//堆排序,不如快速排序
//但是可用其来实现“优先级队列”
int Parent(int i)
{
return ((i+1)/2-1);
}

int Right(int i)
{
return (2*(i+1)-1);
}

int Left(int i)
{
return (2*(i+1));
}

void Max_Heapify(int a[],const int hplast,const int i)
{
int l, r,largest,temp;
l = Left(i);
r = Right(i);
largest = ((l<=hplast) && (a[l]>a[i])) ? l:i;
if((r<=hplast) && (a[r]>a[largest]))
{
largest = r;
}
if(largest != i)
{
temp = a[i];
a[i] = a[largest];
a[largest] = temp;
Max_Heapify(a,hplast,largest);
}

}

void Build_Max_Heap(int a[],const int p, const int r)
{
int i;
for(i = (p+r)/2; i>=p; i--)
{
Max_Heapify(a,r,i);
}
}

void HeapSort(int a[],const int p, int r)
{
int i,temp;
Build_Max_Heap(a,p,r);
for(i = r; i > p; i--)
{
temp = a[p];
a[p] = a[i];
a[i] = temp;
r -= 1;
Max_Heapify(a,r,0);
}
}

PART(3)

/********************************************************************************************
平方阶(O(n2))排序
一般称为简单排序,例如直接插入、直接选择和冒泡排序

********************************************************************************************/
/*插入排序*/
extern int InsertSort(int source[], int array_size)
{
int index = 1; //插入排序
int i, j;
for (i = 1; i < array_size; i++)
{
index = source[i];
j = i;
while ((j > 0) && (source[j - 1] > index))
{
source[j] = source[j - 1];
j--;
}
source[j] = index;
}
return 1;
}
/*冒泡排序*/
extern int BubbleSort(int source[], int array_size)
{
int i, j;
int temp;
for (i = 0; i < array_size; i++)
{
for (j = 0; j < array_size - i - 1; j++)
if (source[j] > source[j + 1])
{
temp = source[j];
source[j] = source[j + 1];
source[j + 1] = temp;
}
}
return 1;
}
/*选择排序*/
extern int SelectSort(int source[], int array_size)
{
int temp, min;
int i, j;
for (i = 0; i < array_size; i++)
{
min = i;//先假设最小下标为i
for (j = i + 1; j < array_size; j++)
if (source[j] < source[min])
min = j;//把i之后的最小值附给min
if (min != i)
{
temp = source[i];
source[i] = source[min];
source[min] = temp;
}//判断min与i是否相等,若相等则说明原假设正确,反之:交换数值
}
return 1;
}
/*********************************************************************************************
线性对数阶(O(nlgn))排序
如快速、堆和归并排序

********************************************************************************************/
/*快速排序接口*/
static int Partition(int source[], int left, int right)
{
int x = source[left];
while (left < right)
{
while (left < right && x <= source[right])
right--;
source[left] = source[right];
while (left < right && x >= source[left])
left++;
source[right] = source[left];
}
source[left] = x;
return left;
}
extern int QuickSort(int source[], int left, int right)
{
int iPos;
if (left >= right)
return 1;
iPos = Partition(source, left, right);
QuickSort(source, left, iPos - 1); // 左边划分
QuickSort(source, iPos + 1, right); // 右边划分
return 1;
}
/*堆排序*/
static void HeapAdjust(int source[], int root, int node)/*root根节点, node节点总数*/
{
//已知source[root..node]中除source[root]之外均满足堆的定义,本函数调整source[root]
//使source[root..node]成为一个大顶堆
int j, rc;
rc = source[root];
for (j = 2 * root; j <= node; j *= 2) //沿关键字叫大的结点向下筛选
{
if (j < node && source[j] < source[j + 1])
++j; //j为关键字较大的记录的下标
if (rc >= source[j])
break; //rc应插入在位置root上
source[root] = source[j];
root = j;
}
source[root] = rc; //插入
}
extern int HeapSort(int source[], int array_size)
{
int i, t;
for (i = array_size / 2; i > 0; --i)
//把a[1..L.length]建成大顶堆
HeapAdjust(source, i, array_size);
for (i = array_size; i > 1; --i)
{
t = source[1]; //将堆顶记录和当前未经排序子序列a[1..i]
source[1] = source[i]; //中的最后一个记录相互交换
source[i] = t;
HeapAdjust(source, 1, i - 1); //将r[1..i-1]重新调整为大顶堆
}
return 1;
}
/**********************************************************************************************
O(n1+£)阶排序
£是介于0和1之间的常数,即0<£<1,如希尔排序
********************************************************************************************/
/*希儿排序*/
extern int ShellSort(int source[], int array_size)
{
int increament;
int e, i, j;

/*初始步长设为n/2*/
for (increament = array_size / 2; increament > 0; increament = increament / 2)
for (j = increament; j < array_size; j++)
{
if (source[j] < source[j - increament])
{
e = source[j];
for (i = j - increament; i >= 0 && source[i] > e; i = i - increament)
source[i + increament] = source[i];
source[i + increament] = e;

}
}
return 1;
}


PART (1)

/*
===============================================
经典排序思想,并用C语言指针实现排序算法
================================================
*/

/*
=============================================================================
相关知识介绍(所有定义只为帮助读者理解相关概念,并非严格定义):
1、稳定排序和非稳定排序

简单地说就是所有相等的数经过某种排序方法后,仍能保持它们在排序之前的相对次序,我们就
说这种排序方法是稳定的。反之,就是非稳定的。
比如:一组数排序前是a1,a2,a3,a4,a5,其中a2=a4,经过某种排序后为a1,a2,a4,a3,a5,
则我们说这种排序是稳定的,因为a2排序前在a4的前面,排序后它还是在a4的前面。假如变成a1,a4,
a2,a3,a5就不是稳定的了。

2、内排序和外排序

在排序过程中,所有需要排序的数都在内存,并在内存中调整它们的存储顺序,称为内排序;
在排序过程中,只有部分数被调入内存,并借助内存调整数在外存中的存放顺序排序方法称为外排序。

3、算法的时间复杂度和空间复杂度

所谓算法的时间复杂度,是指执行算法所需要的计算工作量。
一个算法的空间复杂度,一般是指执行这个算法所需要的内存空间。
================================================================================
*/


/*
================================================
功能:选择排序
输入:数组名称(也就是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述:

在要排序的一组数中,选出最小的一个数与第一个位置的数交换;
然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环
到倒数第二个数和最后一个数比较为止。

选择排序是不稳定的。算法复杂度O(n2)--[n的平方]
=====================================================
*/
void select_sort(int *x, int n)
{
int i, j, min, t;

for (i=0; i<n-1; i++)/*要选择的次数:0~n-2共n-1次*/
{
min = i;/*假设当前下标为i的数最小,比较后再调整*/
for (j=i+1; j<n; j++)/*循环找出最小的数的下标是哪个*/
{
if (*(x+j) < *(x+min))
{
min = j;/*如果后面的数比前面的小,则记下它的下标*/
}
}

if (min != i)/*如果min在循环中改变了,就需要交换数据*/
{
t = *(x+i);
*(x+i) = *(x+min);
*(x+min) = t;
}
}
}


/*
================================================
功能:直接插入排序
输入:数组名称(也就是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述:

在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排
好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数
也是排好顺序的。如此反复循环,直到全部排好顺序。

直接插入排序是稳定的。算法时间复杂度O(n2)--[n的平方]
=====================================================
*/
void insert_sort(int *x, int n)
{
int i, j, t;

for (i=1; i<n; i++)/*要选择的次数:1~n-1共n-1次*/
{
/*
暂存下标为i的数。注意:下标从1开始,原因就是开始时
第一个数即下标为0的数,前面没有任何数,单单一个,认为
它是排好顺序的。
*/
t=*(x+i);
for (j=i-1; j>=0 && t<*(x+j); j--)/*注意:j=i-1,j--,这里就是下标为i的数,在它前面有序列中找插入位置。*/
{
*(x+j+1) = *(x+j);/*如果满足条件就往后挪。最坏的情况就是t比下标为0的数都小,它要放在最前面,j==-1,退出循环*/
}

*(x+j+1) = t;/*找到下标为i的数的放置位置*/
}
}


/*
================================================
功能:冒泡排序
输入:数组名称(也就是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述:

在要排序的一组数中,对当前还未排好序的范围内的全部数,自上
而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较
小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要
求相反时,就将它们互换。

下面是一种改进的冒泡算法,它记录了每一遍扫描后最后下沉数的
位置k,这样可以减少外层循环扫描的次数。

冒泡排序是稳定的。算法时间复杂度O(n2)--[n的平方]
=====================================================
*/

void bubble_sort(int *x, int n)
{
int j, k, h, t;

for (h=n-1; h>0; h=k)/*循环到没有比较范围*/
{
for (j=0, k=0; j<h; j++)/*每次预置k=0,循环扫描后更新k*/
{
if (*(x+j) > *(x+j+1))/*大的放在后面,小的放到前面*/
{
t = *(x+j);
*(x+j) = *(x+j+1);
*(x+j+1) = t;/*完成交换*/
k = j;/*保存最后下沉的位置。这样k后面的都是排序排好了的。*/
}
}
}
}


/*
================================================
功能:希尔排序
输入:数组名称(也就是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述:

在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,
并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为
增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除
多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现
了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中
记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量
对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成
一组,排序完成。

下面的函数是一个希尔排序算法的一个实现,初次取序列的一半为增量,
以后每次减半,直到增量为1。

希尔排序是不稳定的。
=====================================================
*/
void shell_sort(int *x, int n)
{
int h, j, k, t;

for (h=n/2; h>0; h=h/2)/*控制增量*/
{
for (j=h; j<n; j++)/*这个实际上就是上面的直接插入排序*/
{
t = *(x+j);
for (k=j-h; (k>=0 && t<*(x+k)); k-=h)
{
*(x+k+h) = *(x+k);
}
*(x+k+h) = t;
}
}
}


/*
================================================
功能:快速排序
输入:数组名称(也就是数组首地址)、数组中起止元素的下标
================================================
*/
/*
====================================================
算法思想简单描述:

快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟
扫描后,使得排序序列的长度能大幅度地减少。在冒泡排序中,一次
扫描只能确保最大数值的数移到正确位置,而待排序序列的长度可能只
减少1。快速排序通过一趟扫描,就能确保某个数(以它为基准点吧)
的左边各数都比它小,右边各数都比它大。然后又用同样的方法处理
它左右两边的数,直到基准点的左右只有一个元素为止。它是由
C.A.R.Hoare于1962年提出的。

显然快速排序可以用递归实现,当然也可以用栈化解递归实现。下面的
函数是用递归实现的,有兴趣的朋友可以改成非递归的。

快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n),最坏O(n2)

=====================================================
*/
void quick_sort(int *x, int low, int high)
{
int i, j, t;

if (low < high)/*要排序的元素起止下标,保证小的放在左边,大的放在右边。这里以下标为low的元素为基准点*/
{
i = low;
j = high;
t = *(x+low);/*暂存基准点的数*/

while (i<j)/*循环扫描*/
{
while (i<j && *(x+j)>t)/*在右边的只要比基准点大仍放在右边*/
{
j--;/*前移一个位置*/
}

if (i<j)
{
*(x+i) = *(x+j);/*上面的循环退出:即出现比基准点小的数,替换基准点的数*/
i++;/*后移一个位置,并以此为基准点*/
}

while (i<j && *(x+i)<=t)/*在左边的只要小于等于基准点仍放在左边*/
{
i++;/*后移一个位置*/
}

if (i<j)
{
*(x+j) = *(x+i);/*上面的循环退出:即出现比基准点大的数,放到右边*/
j--;/*前移一个位置*/
}
}

*(x+i) = t;/*一遍扫描完后,放到适当位置*/
quick_sort(x,low,i-1);/*对基准点左边的数再执行快速排序*/
quick_sort(x,i+1,high);/*对基准点右边的数再执行快速排序*/
}
}


/*
================================================
功能:堆排序
输入:数组名称(也就是数组首地址)、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述:

堆排序是一种树形选择排序,是对直接选择排序的有效改进。
堆的定义如下:具有n个元素的序列(h1,h2,...,hn),当且仅当
满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)
时称之为堆。在这里只讨论满足前者条件的堆。

由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项。完全二叉树可以
很直观地表示堆的结构。堆顶为根,其它为左子树、右子树。
初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的存储顺序,
使之成为一个堆,这时堆的根节点的数最大。然后将根节点与堆的最后一个节点
交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推,直到只有两个节点
的堆,并对它们作交换,最后得到有n个节点的有序序列。

从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素
交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数
实现排序的函数。

堆排序是不稳定的。算法时间复杂度O(nlog2n)。

*/
/*
功能:渗透建堆
输入:数组名称(也就是数组首地址)、参与建堆元素的个数、从第几个元素开始
*/
void sift(int *x, int n, int s)
{
int t, k, j;

t = *(x+s);/*暂存开始元素*/
k = s;/*开始元素下标*/
j = 2*k + 1;/*右子树元素下标*/

while (j<n)
{
if (j<n-1 && *(x+j) < *(x+j+1))/*判断是否满足堆的条件:满足就继续下一轮比较,否则调整。*/
{
j++;
}

if (t<*(x+j))/*调整*/
{
*(x+k) = *(x+j);
k = j;/*调整后,开始元素也随之调整*/
j = 2*k + 1;
}
else/*没有需要调整了,已经是个堆了,退出循环。*/
{
break;
}
}

*(x+k) = t;/*开始元素放到它正确位置*/
}


/*
功能:堆排序
输入:数组名称(也就是数组首地址)、数组中元素个数
*/
void heap_sort(int *x, int n)
{
int i, k, t;
int *p;

for (i=n/2-1; i>=0; i--)
{
sift(x,n,i);/*初始建堆*/
}

for (k=n-1; k>=1; k--)
{
t = *(x+0);/*堆顶放到最后*/
*(x+0) = *(x+k);
*(x+k) = t;
sift(x,k,0);/*剩下的数再建堆*/
}
}


void main()
{
#define MAX 4
int *p, i, a[MAX];

/*录入测试数据*/
p = a;
printf("Input %d number for sorting :/n",MAX);
for (i=0; i<MAX; i++)
{
scanf("%d",p++);
}
printf("/n");

/*测试选择排序*/


p = a;
select_sort(p,MAX);
/**/


/*测试直接插入排序*/

/*
p = a;
insert_sort(p,MAX);
*/


/*测试冒泡排序*/

/*
p = a;
insert_sort(p,MAX);
*/

/*测试快速排序*/

/*
p = a;
quick_sort(p,0,MAX-1);
*/

/*测试堆排序*/

/*
p = a;
heap_sort(p,MAX);
*/

for (p=a, i=0; i<MAX; i++)
{
printf("%d ",*p++);
}

printf("/n");
system("pause");
}

PART(2)

常用算法(插入,合并,快速,冒泡,堆,shell) C语言实现

#include<stdio.h>
#include<stdlib.h>
void BubbleSort(int a[], const int first, const int last);//冒泡排序
void InsertSort(int a[], const int first, const int last);//插入排序
void SelectSort(int a[], const int first, const int last);//选择排序
void MergeSort(int a[], const int p, const int r);//合并排序
void QuickSort(int a[],const int p,const int r);//快速排序
void ShellSort(int a[],const int p,const int r,const int dlta[],const int t);//希尔排序
void HeapSort(int a[],const int p, int r); //堆排序
void StoogeSort(int a[],const int p,const int r);//Stooge排序(不用)算法复杂度没算清楚

void main()
{
//插入排序算法
int a[11] = {6,4,5,3,2,1};
int dlta[]={9,5,3,2,1};
//BubbleSort(a,0,5);
//InsertSort(a,0,5);
//SelectSort(a,0,5);
//MergeSort(a,0,5);
//QuickSort(a,0,5);
//ShellSort(a,0,5,dlta,5);
HeapSort(a,0,5);
//StoogeSort(a,0,5);


for(int i=0; i<=5;i++)
{
printf("%d ",a[i]);
}

}

/************************冒泡排序***********************/
void BubbleSort(int a[], int first, int last)
{
//实现对数组a[]中a[first]到a[last]升序的“冒泡”排序
int i,j,temp;
for(i=first; i<=last; i++)
{
for(j=first; j< last-i; j++)
{
if(a[j] > a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}

/************************插入排序***********************/
void InsertSort(int a[], int first, int last)
{
//实现对数组a[]中a[first]到a[last]升序的“插入”排序
//最坏情况为n的平方,,多用于小数组
int i,j,temp;
for(i=first+1; i<=last; i++)
{
temp = a[i];
j = i - 1;
while((j >= 0) && (a[j] > temp))
{
a[j+1] = a[j];
j--;
}
a[j+1] = temp;
}
}

/************************选择排序***********************/
void SelectSort(int a[], int first, int last)
{
//实现对数组a[]中a[first]到a[last]升序的“选择”排序
int i, j, temp, num;
for(i=first; i<last; i++)
{
num = i;
for(j=i+1; j<=last; j++)
{
if(a[j] < a[num])
{
num = j;
}
}
if(i != num)
{
temp = a[num];
a[num] = a[i];
a[i] = temp;
}
}
}

/************************合并排序***********************/
void Merge(int a[],const int p,const int q,const int r)
{
//合并排序算法中的实现合并的子程序
int iLLength,iRLength;
int *L, *R, i, j, k;
iLLength = q - p + 1;
iRLength = r - q;
L = (int *)malloc(iLLength*sizeof(int)); //或者 C++中 new int[iLLength];
R = (int *)malloc(iRLength*sizeof(int)); //或者 C++中 new int[iRLength];
if(L == 0 || R== 0)
{
printf("内存分配失败!!!");
return;
}
for(i=0; i<iLLength; i++)
{
L[i] = a[p+i];
}
for(j=0; j<iRLength; j++)
{
R[j] = a[q+j+1];
}
i = 0;
j = 0;
for(k=p; k<=r; k++)
{
if((i<iLLength) && (j<iRLength) && (L[i]<=R[j]) || (j == iRLength))
{
a[k] = L[i];
i++;
}
else if(j<iRLength)
{
a[k] = R[j];
j++;
}
}

free(R);free(L);
}
void MergeSort(int a[],const int p,const int r)
{
//合并排序算法-主程序
//n*lg(n),系数较小
int q;
if(p<r)
{
q = (p+r)/2;
MergeSort(a,p,q);
MergeSort(a,q+1,r);
Merge(a,p,q,r);
}
}

/************************Stooge排序***********************/
void StoogeSort(int a[],const int p,const int r)
{
//Stooge算法
int temp, k;
if(a[p]>a[r])
{
temp = a[p];
a[p] = a[r];
a[r] = temp;
}
if((p+1) >= r)
{
return;
}
k = (r-p+1)/3;
StoogeSort(a,p,r-k);
StoogeSort(a,p+k,r);
StoogeSort(a,p,r-k);
}

/************************快速排序*********************/
int QuickPartition(int a[],const int p,const int r)
{
//快速排序的(关键)分治过程
int temp, x, i, j;
x = a[r];
i = p - 1;
for(j=p; j<r; j++)
{
if(a[j] <= x)
{
i = i + 1;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
temp = a[i+1];
a[i+1] = a[r];
a[r] = temp;
return (i+1);
}
/*
void QuickSort(int a[],const int p,const int r)
{
//快速排序算法-主程序
//与下面的“尾递归实现方法”比较,缺点:右边数组的递归不是必须的,增加了运行堆栈深度和调用开销
int q;
if(p < r)
{
q = QuickPartition(a, p, r);
QuickSort(a, p, q-1);
QuickSort(a, q+1, r);
}
}
*/
void QuickSort(int a[],int p,const int r)
{
//快速排序算法-主程序
//“尾递归实现方法”是对上面的快速排序主程序实现的一种优化
//系数较小,常用大数组
int q;
while(p < r)
{
q = QuickPartition(a, p, r);
QuickSort(a, p, q-1);
p = q + 1;
}
}

/************************希尔排序**********************/
void ShellInsert(int a[],const int p,const int r, int dk)
{
//希尔排序算法的关键子程序-插入排序子程序
int i, j, temp;
for(i=p+dk; i<=r; i++)
{
if(a[i] < a[i-dk])
{
temp = a[i];
for(j=i-dk; ((j>=0) && (temp < a[j])); j -= dk)
{
a[j+dk] = a[j];
}
a[j+dk] = temp;
}
}
}

void ShellSort(int a[],const int p,const int r,const int dlta[],const int t)
{
//希尔排序算法-主程序
//按增量序列dlta[]中的前t个增量,实现对数组a[]中a[p]到a[r]的排序
//dlta[]可能取值如:1,2,3,5,9 dala[k]=2^(t-k+1)-1 其中0<=k<=t<=ld(b-1)
//增量序列的最后一个值必须是1
//增量序列中的值没有除1以外的因子, 其精确时间复杂度:数学上尚未解决的难题
int k;
for(k=0; k<t; k++)
{
ShellInsert(a,p,r,dlta[k]);
}
}

/************************堆排序***********************/
//堆排序,不如快速排序
//但是可用其来实现“优先级队列”
int Parent(int i)
{
return ((i+1)/2-1);
}

int Right(int i)
{
return (2*(i+1)-1);
}

int Left(int i)
{
return (2*(i+1));
}

void Max_Heapify(int a[],const int hplast,const int i)
{
int l, r,largest,temp;
l = Left(i);
r = Right(i);
largest = ((l<=hplast) && (a[l]>a[i])) ? l:i;
if((r<=hplast) && (a[r]>a[largest]))
{
largest = r;
}
if(largest != i)
{
temp = a[i];
a[i] = a[largest];
a[largest] = temp;
Max_Heapify(a,hplast,largest);
}

}

void Build_Max_Heap(int a[],const int p, const int r)
{
int i;
for(i = (p+r)/2; i>=p; i--)
{
Max_Heapify(a,r,i);
}
}

void HeapSort(int a[],const int p, int r)
{
int i,temp;
Build_Max_Heap(a,p,r);
for(i = r; i > p; i--)
{
temp = a[p];
a[p] = a[i];
a[i] = temp;
r -= 1;
Max_Heapify(a,r,0);
}
}

PART(3)

/********************************************************************************************
平方阶(O(n2))排序
一般称为简单排序,例如直接插入、直接选择和冒泡排序

********************************************************************************************/
/*插入排序*/
extern int InsertSort(int source[], int array_size)
{
int index = 1; //插入排序
int i, j;
for (i = 1; i < array_size; i++)
{
index = source[i];
j = i;
while ((j > 0) && (source[j - 1] > index))
{
source[j] = source[j - 1];
j--;
}
source[j] = index;
}
return 1;
}
/*冒泡排序*/
extern int BubbleSort(int source[], int array_size)
{
int i, j;
int temp;
for (i = 0; i < array_size; i++)
{
for (j = 0; j < array_size - i - 1; j++)
if (source[j] > source[j + 1])
{
temp = source[j];
source[j] = source[j + 1];
source[j + 1] = temp;
}
}
return 1;
}
/*选择排序*/
extern int SelectSort(int source[], int array_size)
{
int temp, min;
int i, j;
for (i = 0; i < array_size; i++)
{
min = i;//先假设最小下标为i
for (j = i + 1; j < array_size; j++)
if (source[j] < source[min])
min = j;//把i之后的最小值附给min
if (min != i)
{
temp = source[i];
source[i] = source[min];
source[min] = temp;
}//判断min与i是否相等,若相等则说明原假设正确,反之:交换数值
}
return 1;
}
/*********************************************************************************************
线性对数阶(O(nlgn))排序
如快速、堆和归并排序

********************************************************************************************/
/*快速排序接口*/
static int Partition(int source[], int left, int right)
{
int x = source[left];
while (left < right)
{
while (left < right && x <= source[right])
right--;
source[left] = source[right];
while (left < right && x >= source[left])
left++;
source[right] = source[left];
}
source[left] = x;
return left;
}
extern int QuickSort(int source[], int left, int right)
{
int iPos;
if (left >= right)
return 1;
iPos = Partition(source, left, right);
QuickSort(source, left, iPos - 1); // 左边划分
QuickSort(source, iPos + 1, right); // 右边划分
return 1;
}
/*堆排序*/
static void HeapAdjust(int source[], int root, int node)/*root根节点, node节点总数*/
{
//已知source[root..node]中除source[root]之外均满足堆的定义,本函数调整source[root]
//使source[root..node]成为一个大顶堆
int j, rc;
rc = source[root];
for (j = 2 * root; j <= node; j *= 2) //沿关键字叫大的结点向下筛选
{
if (j < node && source[j] < source[j + 1])
++j; //j为关键字较大的记录的下标
if (rc >= source[j])
break; //rc应插入在位置root上
source[root] = source[j];
root = j;
}
source[root] = rc; //插入
}
extern int HeapSort(int source[], int array_size)
{
int i, t;
for (i = array_size / 2; i > 0; --i)
//把a[1..L.length]建成大顶堆
HeapAdjust(source, i, array_size);
for (i = array_size; i > 1; --i)
{
t = source[1]; //将堆顶记录和当前未经排序子序列a[1..i]
source[1] = source[i]; //中的最后一个记录相互交换
source[i] = t;
HeapAdjust(source, 1, i - 1); //将r[1..i-1]重新调整为大顶堆
}
return 1;
}
/**********************************************************************************************
O(n1+£)阶排序
£是介于0和1之间的常数,即0<£<1,如希尔排序
********************************************************************************************/
/*希儿排序*/
extern int ShellSort(int source[], int array_size)
{
int increament;
int e, i, j;

/*初始步长设为n/2*/
for (increament = array_size / 2; increament > 0; increament = increament / 2)
for (j = increament; j < array_size; j++)
{
if (source[j] < source[j - increament])
{
e = source[j];
for (i = j - increament; i >= 0 && source[i] > e; i = i - increament)
source[i + increament] = source[i];
source[i + increament] = e;

}
}
return 1;
}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics