数据结构与算法学习--排序
排序是最基本的算法,在项目开发中经常遇到,也是面试环节中考察最多的。
1、冒泡、插入、选择三种排序的比较及代码实现
“有序度”和“逆序度”:对于一个不完全有序的数组,如4,5,6,3,2,1,有序元素对为3个(4,5),(4,6),(5,6),有序度为3,逆序度为12;对于一个完全有序的数组,如1,2,3,4,5,6,有序度就是n*(n-1)/2,也就是15,称作满有序度;逆序度=满有序度-有序度;冒泡排序、插入排序交换(或移动)次数=逆序度。
最好情况下初始有序度为n*(n-1)/2,最坏情况下初始有序度为0,则平均初始有序度为n*(n-1)/4,即交换次数为n*(n-1)/4,因交换次数<比较次数<最坏情况时间复杂度,所以平均时间复杂度为O(n^2)。
思考题:
1、冒泡排序和插入排序时间复杂度都是0(n^2),都是稳定性及原地排序。为什么插入排序效率更高一些。
从数据分析,原始数据的逆序度时固定的。两种排序在交换和移动的次数是一致的。
从代码分析上看,冒泡排序的数据交换要比插入排序的数据移动要复杂,冒泡排序需要3个赋值操作,而插入排序只需要1个,所以在对相同数组进行排序时,冒泡排序的运行时间理论上要长于插入排序。
2、我们一般排序都是使用数组来实现的,如果使用链表,排序工作如果实现呢。
觉得应该有个前提,是否允许修改链表的节点value值,还是只能改变节点的位置。一般而言,考虑只能改变节点位置,冒泡排序相比于数组实现,比较次数一致,但交换时操作更复杂;插入排序,比较次数一致,不需要再有后移操作,找到位置后可以直接插入,但排序完毕后可能需要倒置链表;选择排序比较次数一致,交换操作同样比较麻烦。综上,时间复杂度和空间复杂度并无明显变化,若追求极致性能,冒泡排序的时间复杂度系数会变大,插入排序系数会减小,选择排序无明显变化。
/*************************************************************************
> File Name: sorts_jinshaohui.c
> Author: jinshaohui
> Mail: [email protected]
> Time: 18-10-19
> Desc:
************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SWAP(a,b) \
do{\
(a) ^= (b);\
(b) ^= (a);\
(a) ^= (b);\
}while(0)
/*冒泡排序*/
void bubble_sort(int a[],int size)
{
int i = 0;
int j = 0;
int swap_flg = 0;
if (size < 1)
{
return;
}
for (i = size - 1; i > 0; i--)/*排序的趟数*/
{
swap_flg = 0;/*每次设置交换标识为0*/
for (j = 0; j < i; j++)/*本趟排序的遍历元素个数*/
{
if (a[j] > a[j + 1])
{
SWAP(a[j],a[j+1]);
swap_flg = 1;
}
}
/*本趟数,无数据交换的话,说明已经有序,直接退出*/
if (swap_flg == 0)
{
break;
}
}
return;
}
/*插入排序*/
void insert_sort(int a[],int size)
{
int i = 0;
int j = 0;
int key = 0;
for (i = 1; i < size; i ++)/*需要插入的元素个数*/
{
key = a[i];/*保存插入的元素数据*/
j = i - 1;
/* i 之前的元素都是有序的,找到比key小的插入到他后面,
* 比key大的,需要往后挪一个位置*/
while((j >= 0) && (a[j] > key))
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
return;
}
/*选择排序*/
void select_sort(int a[],int size)
{
int i = 0;
int j = 0;
int min = 0;
for (i = 0; i < size - 1; i++)
{
min = i;
for (j = i + 1; j < size; j++)
{
if (a[j] < a[min])
{
min = j;
}
}
if (min != i)
{
SWAP(a[i],a[min]);
}
}
return;
}
void dump(int a[],int size)
{
int i = 0;
printf("\r\n");
for (i = 0; i < size; i++ )
{
printf("%d ",a[i]);
}
printf("\r\n");
return;
}
int main()
{
int a[10] = {9,11,4,15,16,3,20,44,5,10};
//bubble_sort(a,sizeof(a)/sizeof(int));
//insert_sort(a,sizeof(a)/sizeof(int));
select_sort(a,sizeof(a)/sizeof(int));
dump(a,sizeof(a)/sizeof(int));
return 0;
}