数据结构之排序算法(C语言)
一.冒泡排序
冒泡排序是最简单的排序之一了，其大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。这个过程类似于水泡向上升一样，因此而得名。举个栗子，对5,3,8,6,4这个无序序列进行冒泡排序。首先从前向后冒泡，5和3比较，换数，序列变成3,5,8,6,4。同理5和8比较，不用交换,还是3,5,8,6,4。8和6比较,交换，变成3,5,6,8,4。8最后和4比较,交换,得到3,5,6,4,8。这样一次冒泡就完了，把最大的数8排到最后面了。对剩下的序列依次冒泡就会得到一个有序序列。冒泡排序的时间复杂度为O(n^2)。
代码实现:
/*冒泡排序*/#include
<stdio.h>void bubble_sort(int *a,int len)
{
int i,j,t;
for(i=0;i<len-1;i++)//整体比较次数 (比如两个数只需要比较一次)所以要减一
for(j=0;j<len-i-1;j++)//每一次需要哪几个数来比,减掉1个(比如两个数只需要比较一次),再减掉已经排好了的数.
if(a[j]>a[j+1])
{
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
int main()
{
int a[5] = {5,3,8,6,4};
bubble_sort(a,5);
for(i=0;i<5;i++)
printf("%d ",a[i]);
}
二.选择排序
选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。举个栗子，对5,3,8,6,4这个无序序列进行简单选择排序，首先要选择5以外的最小数来和5交换，也就是选择3和5交换，一次排序后就变成了3,5,8,6,4.对剩下的序列一次进行选择和交换，最终就会得到一个有序序列。其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。选择排序的时间复杂度为O(n^2)。
代码实现:
/*选择排序,av18176082*/#include
<stdio.h>void elect_sort(int *a,int len)
{
int i,j,t,k;
for(i=0;i<len-1;i++)//一共要拿len-1个数出来和其他数比
{
k=i;//让k记住这个数
for(j=i+1;j<len;j++)//让k这个数和其他未排序的数比
if(a[k]>a[j])
{
t = a[k];
a[k] = a[j];
a[j] = t;
}
}
}
int main()
{
int a[5] = {5,3,8,6,4},i;
elect_sort(a,5);
for(i=0;i<5;i++)
printf("%d ",a[i]);
return0;
}
/*void sort(int *a,int len)
{
int i,j,t,k;
for(i=0;i<len-1;i++)
for(j=i+1;j<len;j++)
{
if(a[i]<a[j])
{
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
*/
三.插入排序
插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。相信大家都有过打扑克牌的经历，特别是牌数较大的。在分牌时可能要整理自己的牌，牌多的时候怎么整理呢？就是拿到一张牌，找到一个合适的位置插入。这个原理其实和插入排序是一样的。举个栗子，对5,3,8,6,4这个无序序列进行简单插入排序，首先假设第一个数的位置时正确的，想一下在拿到第一张牌的时候，没必要整理。然后3要插到5前面，把5后移一位，变成3,5,8,6,4.想一下整理牌的时候应该也是这样吧。然后8不用动，6插在8前面，8后移一位，4插在5前面，从5开始都向后移一位。注意在插入一个数的时候要保证这个数前面的数已经有序。简单插入排序的时间复杂度也是O(n^2)。
代码实现:
#include <stdio.h>void insert_sort(int *a,int len)
{
int i,j,tmp;
for(i=1;i<len;i++)//拿这么多个数来插入,第一个数本身就是有序序列,不需要比较
{
tmp = a[i];
j = i-1;//j是有序序列最后一个数的下标
while(j>=0&&tmp<a[j])//升序
{
a[j+1] = a[j];//不是插入位置,数往后移动
j--;
}
a[j+1] = tmp;
}
}
int main(int argc, char *argv[])
{
int a[5]={5,3,8,6,4},i;
insert_sort(a,5);
for(i=0;i<5;i++)
printf("%d ",a[i]);
return0;
}
/*void sort(int *a,int len)
{
int i,j,tmp;
for(i=1;i<len;i++)
{
tmp = a[i];
for(j=i-1;j>=0&&a[j]>tmp;j--)
a[j+1] = a[j];
a[j+1] = tmp;
}
}
*/四.快速排序
快速排序一听名字就觉得很高端，在实际应用当中快速排序确实也是表现最好的排序算法。快速排序虽然高端，但其实其思想是来自冒泡排序，冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端，而快速排序是比较和交换小数和大数，这样一来不仅把小数冒泡到上面同时也把大数沉到下面。
举个栗子：对5,3,8,6,4这个无序序列进行快速排序，思路是右指针找比基准数小的，左指针找比基准数大的，交换之。
5,3,8,6,4 用5作为比较的基准，最终会把5小的移动到5的左边，比5大的移动到5的右边。
5,3,8,6,4 首先设置low,high两个指针分别指向两端，high指针先扫描（思考一下为什么？）4比5小停止。然后low扫描，8比5大停止。交换low,high位置。
5,3,4,6,8 然后j指针再扫描，这时j扫描4时两指针相遇。停止。然后交换4和基准数。
4,3,5,6,8 一次划分后达到了左边比5小，右边比5大的目的。之后对左右子序列递归排序，最终得到有序序列。
上面留下来了一个问题为什么一定要j指针先动呢？首先这也不是绝对的，这取决于基准数的位置，因为在最后两个指针相遇的时候，要交换基准数到相遇的位置。一般选取第一个数作为基准数，那么就是在左边，所以最后相遇的数要和基准数交换，那么相遇的数一定要比基准数小。所以j指针先移动才能先找到比基准数小的数。
快速排序是不稳定的，其时间平均时间复杂度是O(nlgn)。
实现代码:
#include <stdio.h>void quick_sort(int *a,int low,int high);
int find_pos(int *a,int low,int high);
int main(int argc, char *argv[])
{
int a[5] = {5,3,8,6,4},i;
quick_sort(a,0,4);
for(i=0;i<5;i++)
printf("%d ",a[i]);
return0;
}
void quick_sort(int *a,int low,int high)
{
int pos;
if(low<high)
{
pos = find_pos(a,low,high);
quick_sort(a,low,pos-1);
quick_sort(a,pos+1,high);
}
}
int find_pos(int *a,int low,int high)//寻找第一个数的准确位置
{
int val = a[low];
while(low<high)
{
while(low<high && a[high]>=val)//(low<high)这个条件不能少
high--;
a[low] = a[high];
while(low<high && a[low]<=val)
low++;
a[high] = a[low];
}
//循环完后high = low
a[high] = val;
return high;
}
//视频讲解:av6159200 p76
五.希尔排序
希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。简单的插入排序中，如果待排序列是正序时，时间复杂度是O(n)，如果序列是基本有序的，使用直接插入排序效率就非常高。希尔排序就利用了这个特点。基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。
实现代码:
#include <stdio.h>void shell_sort(int *a,int len)
{
int i,j,D,tmp;
for(D=len/2;D>0;D=D/2)//控制增量序列,循环里面其实就是一个插入排序
{ //直接插入排序的间隔为1,这里是D,也就是是在将间隔为D的数列进行排序
for(i=D;i<len;i++)
{
{
tmp = a[i];
for(j=i-D;j>=0&&a[j]>=tmp;j=j-D)//j为有序序列的最后一个元素的下标
a[j+D] = a[j];
}
a[j+D] = tmp;
}
}
}
int main(int argc, char *argv[])
{
int a[5] = {5,3,8,6,4};
shell_sort(a,5);
int i;
for(i=0;i<5;i++)
printf("%d ",a[i]);
return0;
}
六.堆排序
堆排序是利用二叉树来进行排序,将数组的下标来作为二叉树的下标.0下标无效,不存放有效数.然后将二叉树排成一个最大堆或者最小堆,排好后将根节点(最大值或最小值)和数组的最后一个元素依次进行替换;这样数组就变成了一个有序序列.
堆排序的时间复杂度为O（nlogn） 构建堆的过程的时间复杂度为n，调堆的时间复杂度为logn
实现代码:
#include<stdio.h>void swap(int *a,int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void percdown(int a[],int node,int len)
{
int i;
int temp = a[node];
for(i=2*node;i<=len;i*=2)
{
if(i<len&&a[i]<a[i+1])//两个孩子相比较
i++;//i指向最大的孩子
if(a[i]>temp)//最大的孩子和双亲进行比较
{
a[node] = a[i];//让最大的孩子的值赋值给双亲结点
node = i;//node就指向换数的那个孩子
/*这两句最难理解,但是又很好理解其实就是一个换数的过程*/
}
}
a[node] = temp;
}
void heap_sort(int *a,int len)
{
int i;
for(i=len/2;i>0;i--)//len/2:最后一个双亲结点 *从下往上,从右往左*
percdown(a,i,len);//len:当前堆里的元素个数
for(i=len;i>1;i--)
{
swap(&a[1],&a[i]);
percdown(a,1,i-1);
}
}
int main()
{
int a[5] = {5,3,8,6,4};
heap_sort(a,5);
int i;
for(i=0;i<5;i++)
printf("%d ",a[i]);
return0;
}
以上是 数据结构之排序算法(C语言) 的全部内容， 来源链接： utcz.com/z/509210.html
