一、冒泡排序
主要思想，假设有一个数组a[n]，有n个元素。初始阶段无序区是n。从无序区第一个元素开始，对每两个相邻的元素比较，较大的向后移动。一趟冒泡排序结束后确定一个在无序区中最大元素在整个序列的位置，无序区相应的减小1。直到无序区为1，也就是无序区内不再进行元素交换为止。简言之，就是一趟冒泡排序把较大的元素向数组后部移动。
void bubble_sort(int *ar,int ilen)
{
int i, j, val;
for(i = 0; i < ilen; i++) {
for (j = 0; j < ilen - i - 1; j++){
if(ar[j] > ar[j+1]) {
val = ar[j+1];
ar[j+1] = ar[j];
ar[j] = val;
}
}
}
}
时间复杂度 O(n2)
空间复杂度O(1)
稳定性排序
二、快速排序
主要思想 分而治之。假设a[n]数组，取第一个元素为基准，把数组分成左右两个子序列，左边的小于等于基准，右边的大于等于基准，基准则在有序序列的正确位置。然后再分别对产生这两个子列表按照前面的方法排序，直到子列表只有一个元素为止。
还有重要的一点是如何把左右子序列通过基准划分出来。第一步取数组的上界和下届，即i = 0, j = ilen -1；选取第一个元素为基准记录保存于val。第二步，让j从右向左扫描，直到找到第一个小于基准的元素a[j]，将a[j]移到a[i]的位置上，这相当于a[j]和基准进行了交换，使小于基准的元素移到了基准的左边，交换后a[j]相当于基准的位置；然后让i从i+1的位置左到有扫描，直到找到第一个大于基准的元素a[i]，将a[i]移动到a[j]的位置，这相当于a[i]和基准做了交换，使大于基准的元素都移动了基准的右边，交换后a[i]相当于基准的位置；接着让j从j-1的位置开始继续向左扫描，如此交替改变扫描方向，从两端向中间靠拢，直至i==j时，i便是基准的最终位置，将基准放在此位置上就完成了一次划分。
int quick_sort(int *ar, int ilen)
{
int *lp, *rp, val, i, j;
if (ilen <= 1) return 0;
val = ar[0];
i = 0;
j = ilen -1;
while(i < j){
while ((i < j) && (ar[j] > val)) j--;
if(i < j) ar[i++] = ar[j];
while ((i < j) && (ar[i] < val)) i++;
if (i
}
ar[i] = val;
lp = ar;
quick_sort(lp,i);
if((i + 1) < ilen){
quick_sort(rp, ilen - i -1);
}
return 0;
}
时间复杂度 O(nlgn)
空间复杂度O(1)
非稳定性排序
阅读(2299) | 评论(0) | 转发(0) |
