一、希尔排序(不稳定)
1、基本思想:将待排序列划分为若干组,在每一组内进行插入排序,以使整个序列基本有序,然后再对整个序列进行插入排序。
2、示例
例如:将n 个数据元素分成d 个子序列:
{ R[1],R[1+d],R[1+2d],…,R[1+kd] }
{ R[2],R[2+d],R[2+2d],…,R[2+kd] }
…
{ R[d],R[2d],R[3d],…,R[kd],R[(k+1)d] }
其中,d 称为增量,它的值在排序过程中从大到小逐渐缩小,直至最后一趟排序减为1。
3、实现
#include
void printarray(int array[],int len)
{
int i = 0;
for(i = 0; i < len;i++){
printf("%d ",array[i]);
}
printf("\n");
}
void ShellSort(int array[],int len)
{
int i = 0;
int j = 0;
int k = -1;
int temp = -1;
int gap = len;
/*
for(i = 1;i < len;i++){
k = i;
temp = array[k];
for(j = i-1;(j >= 0)&& (array[j] > temp);j--){
array[j+1] = array[j];
k = j;
}
array[k] = temp;
}
*/
do{
gap = gap / 3 + 1;//gap 最后收敛于1
for(i = gap; i < len; i += gap){
k = i;
temp = array[k];
for(j = i - gap; (j >= 0) && (array[j] > temp);j -= gap){
array[j + gap] = array[j];
k = j;
}
array[k] = temp;
}
}while(gap > 1);
}
int main()
{
int array[] = {21,25,49,25,16,8};
int len = sizeof(array) / sizeof(*array);
printarray(array,len);
ShellSort(array,len);
printarray(array,len);
return 0;
}
二、快速排序(不稳定)
1、基本思想
1)任取待排序序列中的某个数据元素作为基准,按照该元素的关键字大小将整个序列划分为左右两个子序列:
---左侧子序列中的所有元素都小于或等于基准元素
---右侧子序列中的所有元素都大于基准元素
---基准元素排在这两个子序列中间
2)分别对这两个子序列重复执行上述方法,直到所有的对象都排在相对于的位置上为止。
2、实现
#include
void printarray(int array[],int len)
{
int i = 0;
for(i = 0; i < len;i++){
printf("%d ",array[i]);
}
printf("\n");
}
void swap(int array[],int i,int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
int partition(int array[],int low,int high)
{
int pv = array[low];
while(low < high){
while((low < high) && (array[high] >= pv)){
high--;
}
swap(array,low,high);
while((low < high) && (array[low] <= pv)){
low++;
}
swap(array,low,high);
}
return low;
}
void QSort(int array[],int low,int high)
{
if(low < high){
int pivot = partition(array,low,high);
QSort(array,low,pivot-1);
QSort(array,pivot+1,high);
}
}
void QuickSort(int array[],int len)
{
QSort(array,0,len-1);
}
int main()
{
int array[] = {21,25,49,25,16,8};
int len = sizeof(array) / sizeof(*array);
printarray(array,len);
QuickSort(array,len);
printarray(array,len);
return 0;
}
三、归并排序(稳定)
1、基本思想
将两个或两个以上的有序序列合并成一个新的有序序列:
有序序列V[1] …V[m]和V[m+1] …V[n]合并为V[1] …V[n],这种归并方法称为2路归并。
将3个有序序列归并为一个新的有序序列,称为3路归并。
将多个有序序列归并为一个新的有序序列,称为多路归并。
2、实现
#include
#include
void printarray(int array[],int len)
{
int i = 0;
for(i = 0; i < len;i++){
printf("%d ",array[i]);
}
printf("\n");
}
Merge(int src[],int des[],int low,int mid,int high)
{
int i = low;
int j = mid + 1;
int k = low;
while((i <= mid) && (j <= high)){
if(src[j] < src[i]){
des[k++] = src[j++];
}else{
des[k++]= src[i++];
}
}
while(i <= mid){
des[k++]= src[i++];
}
while(j <= high){
des[k++]= src[j++];
}
}
void Msort(int src[],int des[],int low,int high,int max)
{
if(low == high){
des[low] = src[low];
}else{
int mid = (low + high) / 2;
int* space = (int*)malloc(sizeof(int)*max);
if(space != NULL){
Msort(src,space,low,mid,max);
Msort(src,space,mid+1,high,max);
Merge(space,des,low,mid,high);
}
free(space);
}
}
void MergeSort(int array[],int len)
{
Msort(array,array,0,len - 1,len);
}
int main()
{
int array[] = {21,25,49,25,16,8};
int len = sizeof(array) / sizeof(*array);
printarray(array,len);
MergeSort(array,len);
printarray(array,len);
return 0;
}
四、总结
希尔排序,快速排序和归并排序将排序算法的时间复杂度提高到了O(n*logn)
希尔排序和快速排序的排序结果是不稳定的
归并排序的排序结果是稳定的
阅读(526) | 评论(0) | 转发(0) |