0.排序的复杂度比较
排序
1.冒泡排序
冒泡排序基础版本1
//冒泡排序
#include <stdio.h>
#include <windows.h>
void BubbleSort(int *a,int len)
{
int i,j,temp;
for(i=0;i<len-1;i++)
{
for(j=i+1;j<len;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
}
void show(int *a,int len)
{
int i;
for(i=0;i<len;i++)
{
printf("%d ",a[i]);
}
printf("\n\n");
}
int main()
{
printf("------冒泡排序------\n");
int a[10]={80,56,23,11,54,20,79,99,35,1};
printf("排序前数组a为:");
show(a,10);
printf("排序后数组a为:");
BubbleSort(a,10);
show(a,10);
system("pause");
return 1;
}
冒泡排序基础版1
正宗的冒泡排序算法
//正宗的冒泡排序
void BubbleSort2(int *a,int len)
{
int i,j,temp;
for(i=0;i<len-1;i++)
{
for(j=len-1;j>i;j--)
{
if(a[j-1]>a[j])
{
temp=a[j-1];
a[j-1]=a[j];
a[j]=temp;
}
}
}
}
正宗冒泡排序优化版本
//正宗的冒泡排序 优化版
void BubbleSort3(int *a,int len)
{
int i,j,temp;
int flag = 1;
for(i=0;i<len-1&&flag;i++)
{
flag = 0;//没有数据交换
for(j=len-1;j>i;j--)
{
if(a[j-1]>a[j])
{
temp=a[j-1];
a[j-1]=a[j];
a[j]=temp;
flag = 1;//有数据交换
}
}
}
}
2.选择排序
//选择排序算法
void SelectSort(int a[],int len)
{
int i,j,temp;
int min;
for(i=0;i<len-1;i++)
{
min =i;//先把当前当做最小值
for(j=i+1;j<len;j++)
{
if(a[min]>a[j])
min=j; //向后遍历，获得最小值
}
if(min != i)
{
temp=a[min];
a[min]=a[i];
a[i]=temp;
}
}
}
3.插入排序算法
//插入排序
void InsertSort(int a[],int len)
{
int i,j,temp;
for(i=1;i<len;i++)
{
if(a[i-1]>a[i])
{
temp = a[i];//记录当前a[i]的值
printf("当前比较的a[%d]=%d \n",i,a[i]);
for(j=i-1;a[j]>temp&&j>=0;j--)
{
a[j+1]=a[j];//元素往后移动
}
printf("赋值 a[%d]=%d \n",j+1,temp);
a[j+1]=temp;//插入当前位置
}
}
}
4.希尔排序
在插入排序的基础上进行修改
//希尔排序
void ShellSort(int a[],int len)
{
int i,j,temp;
int gap = len;
do
{
gap = gap/3+1;//增量序列
for(i=gap;i<len;i++)
{
if(a[i-gap]>a[i])
{
temp = a[i];
for(j=i-gap;j>=0&&a[j]>temp;j-=gap)
{
a[j+gap]=a[j];//记录后移，寻找合适的位置插入
}
a[j+gap]=temp;//插入数据
}
}
}while(gap>1);
}
5.堆排序
//堆排序
#include <stdio.h>
#include <windows.h>
//打印数组
void show(int *a,int len)
{
int i;
for(i=1;i<=len;i++)
{
printf("%d ",a[i]);
}
printf("\n\n");
}
//交换数据
void swap(int a[],int i,int j)
{
int temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
//堆调整
void HeapAdjust(int a[],int s,int len)
{
int i,temp;
temp = a[s];
for(i=2*s;i<=len;i*=2)
{
if(i<len && a[i]<a[i+1])//左子节点>右子节点
{
i++;//i移动到右节点
}
if(temp >=a[i])//父节点的值大于左右节点的值
break;//无需移动
a[s] = a[i];//把最大子节点的值赋给父节点
s=i;//s移动到i子节点
}
a[s]=temp;//插入
}
//堆排序
void HeapSort(int a[],int len)
{
int i;
//先构建堆
for(i=len/2;i>0;i--)
{
HeapAdjust(a,i,len);
}
//堆排序:把根节点和最后一个节点互换
for(i=len;i>1;i--)
{
swap(a,1,i);
HeapAdjust(a,1,i-1);//重新调整堆
}
}
int main()
{
printf("----------------堆排序----------------\n");
//a[0]用于存放数组长度，实际从a[1]开始
int a[]={10,80,56,23,11,54,20,79,99,35,1};
printf("排序前数组a为:");
show(a,a[0]);
printf("排序后数组a为:");
HeapSort(a,a[0]);
show(a,a[0]);
system("pause");
return 1;
}
HeapSort
6.归并排序
**1.归并排序-递归实现 **
//堆排序
#include <stdio.h>
#include <windows.h>
//打印数组
void show(int *a,int len)
{
int i;
for(i=0;i<len;i++)
{
printf("%d ",a[i]);
}
printf("\n\n");
}
//进行归并
void merging(int *a,int a_len,int *b,int b_len)
{
int i,j,k;
i=j=k=0;
int temp[20];
while(i<a_len&&j<b_len)
{
if(a[i]<b[j])
{
temp[k++] = a[i++];
}
else
{
temp[k++] = b[j++];
}
}
while(i<a_len)
{
temp[k++] = a[i++];
}
while(j<b_len)
{
temp[k++] = b[j++];
}
for(i=0;i<a_len+b_len;i++)
{
a[i]=temp[i];
}
}
//归并排序
void MergeSort(int a[],int len)
{
if(len>1)
{
int *list1 =a;
int list1_size = len/2;
int * list2 = a+len/2;
int list2_size = len - list1_size;
MergeSort(list1,list1_size);
MergeSort(list2,list2_size);
merging(list1,list1_size,list2,list2_size);
}
}
int main()
{
printf("----------------归并排序----------------\n");
//a[0]用于存放数组长度，实际从a[1]开始
int a[]={10,80,56,23,11,54,20,79,99,35,1};
printf("排序前数组a为:");
show(a,a[0]);
printf("排序后数组a为:");
MergeSort(a,a[0]);
show(a,a[0]);
system("pause");
return 1;
}
归并排序-递归实现
2.归并排序-迭代实现
7.快速排序
1.快速排序的基本版
//堆排序
#include <stdio.h>
#include <windows.h>
//打印数组
void show(int *a,int len)
{
int i;
for(i=0;i<len;i++)
{
printf("%d ",a[i]);
}
printf("\n\n");
}
void swap(int *a,int low,int high)
{
int temp;
temp = a[low];
a[low] = a[high];
a[high] = temp;
}
//计算基准点，小的放在基准点左边，大的放在基准点右边
int partition(int *a,int low,int high)
{
int p = a[low];//基准点默认为a[low]
while(low<high)
{
while(low<high&&a[high]>=p)
{
high--;
}
swap(a,low,high);
while(low<high&&a[low]<=p)
{
low ++;
}
swap(a,low,high);
}
return low;
}
//快速排序的实现
void QSort(int *a,int low,int high)
{
int point;//基准点
if(low < high)
{
point = partition(a,low,high);//计算基准点
QSort(a,low,point-1);//排序左边
QSort(a,point+1,high); //排序右边
}
}
//快速排序
void QuickSort(int a[],int len)
{
QSort(a,0,len-1);
}
int main()
{
printf("----------------快速排序----------------\n");
//a[0]用于存放数组长度，实际从a[1]开始
int a[]={10,80,56,23,11,54,20,79,99,35,1};
printf("排序前数组a为:");
show(a,a[0]);
printf("排序后数组a为:");
QuickSort(a,a[0]);
show(a,a[0]);
system("pause");
return 1;
}
快速派排序1
网友评论