常用排序算法整理分享(快速排序算法、希尔排序)
整理了几个排序算法,通过测试来看,最快的还是快速排序算法,简直不是一个数量级的速度。
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <time.h>
#include <unistd.h>
//一些排序算法整理
//插入排序算法
//直接插入排序
void
direct_insert_sort(int *a,int len)
{
//思路:最后一个依次和前面的进行比较
//将满足的条件的往后移动,当然是从头
//开始且是从最小比较数组开始逐渐扩大
//到整个数组
int i,j,temp;
for(i = 1;i < len;++i) {
//获取最后一个索引数据
temp = a[i];
for(j = i - 1;j >= 0;--j) {
//从倒数第二个开始
if(a[j] > temp)//升序排列
a[j + 1] = a[j];
else
break;//立刻退出
}
//将最后一个位置插入到合适的位置
a[j + 1] = temp;
}
}
//希尔排序
void
shell_insert_sort(int *a,int len)
{
//思路:就是比直接插入排序多了层
//循环,这层循环是用来控制步进按
//照算法的本来思路是这样可以减少
//交换次数
int i,j,h,temp;
for(h = len / 2;h > 0;h /= 2) {
//内层其实本质还是直接插入
//算法思路
//注意下i += h和i++两者对算
//法的影响
for(i = h;i < len;i += h) {
//获取最后一个索引的值
temp = a[i];
for(j = i - h;j >= 0;j -= h) {
if(a[j] > temp)//升序排列
a[j + h] = a[j];
else
break;
}
//将找到的位置插入最后一个索引
a[j + h] = temp;
}
}
}
//选择排序
//冒泡排序
void
bubble_swap_sort(int *a,int len)
{
//思路:从数组最后开始两两比较
//将底层满足要求的数据逐渐交换
//到上层,可能导致交换次数太多
int i,j,temp;
//如果一次冒泡中没有发生交换可
//以认为此次排列已经结束
bool exchange = false;
for(i = 0;i < len - 1;++i) {
for(j = len - 1;j > i;--j) {
//满足条件的就进行交换
if(a[j] < a[j - 1]) {
temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
exchange = true;
}
}
if(exchange)
exchange = false;
else
break;
}
}
//快速排序
void
quick_swap_sort(int *a,int low,int high)
{
//思路:从数组中找一个值
//然后排列数组使其两边要
//么大于要么小于这个值,
//然后递归下去排序
//优势在于每次找中间值可
//以交换很多次。
int _low,_high,qivot;
if(low < high) {
_low = low;
_high = high;
//这里从最后一个开始
qivot = a[low];
//找中间值的办法就是逐渐逼近
//从头尾两端开始逼近,顺便也
//排序了
while(_low < _high) {
//既然是从low开始,那么首先
//就从high找小于qivot的(升
//序排列)
while(_low < _high && a[_high] > qivot)
--_high;//逐渐向中间逼近
if(_low < _high)//必然是找到了a[_high] > qivot的情况
a[_low++] = a[_high];
//这下a[_high]空出位置来了,所以从low找
//比qivot大的数据
while(_low < _high && a[_low] < qivot)
--_low;//逼近中间
if(_low < _high)
a[_high--] = a[_low];
}
//最后_low == _high那么这个位置就是qivot的位置
a[_low] = qivot;
//递归下去
quick_swap_sort(a,low,_high - 1);
quick_swap_sort(a,_low + 1,high);
}
}
//选择排序
//直接选择排序
void
direct_select_sort(int *a,int len)
{
//思路:就是遍历数组找到极值
//放到头或者尾,这样逐渐缩小
//范围到最小比较数组
int i,j,pos,temp;
for(i = 0;i < len - 1;++i) {
//从头开始获取一个值假设为极值
pos = i;
for(j = i + 1;j < len;++j) {
//满足条件
if(a[pos] > a[j])//升序
pos = j;
}
if(pos != i) {
//进行交换
temp = a[pos];
a[pos] = a[i];
a[i] = temp;
}
}
}
void
disp(int *a,int len)
{
int i = 0;
for(;i < len;i++) {
if(i != 0 && i % 16 == 0)
printf("\n");
printf(" %d",a[i]);
}
printf("\n");
}
#define TEST_ARRAY_LEN 100000
#define TEST_COUNT 1
int
main(int argc,char *argv[])
{
//int a[] = {1,8,4,0,9,6,3,7,2,18,74,5,64,12,39};
//int len = sizeof(a) / sizeof(a[0]);
//direct_insert_sort(a,len);
//shell_insert_sort(a,len);
//bubble_swap_sort(a,len);
//quick_swap_sort(a,0,len - 1);
//direct_select_sort(a,len);
disp(a,len);
return 0;
}
相关文章
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
图文详解Heap Sort堆排序算法及JavaScript的代码实现
这篇文章以图文详解Heap Sort堆排序算法及JavaScript的代码实现,堆排序算法基于类二叉树的堆数据结构,需要的朋友可以参考下...2016-05-05- 这篇文章主要为大家详细介绍了C/C++实现八大排序算法汇总,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C语言演示对归并排序算法的优化实现,归并排序的最差时间复杂度为(n\log n),最优时间复杂为(n),存在可以改进的空间,需要的朋友可以参考下...2020-04-25
- 冒泡排序和快速排序算法在开发应用中各有优点了,下面我们来看几个关于php排序的几个例子。 使用PHP描述冒泡排序和快速排序算法,对象可以是一个数组。 使用PHP描...2016-11-25
- 这篇文章主要为大家详细介绍了C++排序算法之插入排序,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
stl常用算法(Algorithms)介绍(stl排序算法、非变序型队列)
这篇文章主要介绍了stl常用算法(Algorithms)介绍(stl排序算法、非变序型队列),需要的朋友可以参考下...2020-04-25- function quickSort(&$data, $beg, $end) 02 { 03 if ($end > $beg) { 04 $piv = $data[$beg]; 05 $k = $beg + 1; 06 $r = $end; 07 while ($k < $r) { 08 if...2016-11-25
- 这篇文章主要介绍了堆排序算法(选择排序改进),有需要的朋友可以参考一下...2020-04-25
- 这篇文章主要介绍了一些常用排序算法整理,插入排序算法、直接插入排序、希尔排序、选择排序、冒泡排序等排序,需要的朋友可以参考下...2020-04-25
PHP常用排序算法实例小结【基本排序,冒泡排序,快速排序,插入排序】
小编推荐的这篇文章介绍了PHP常用排序算法实例小结,基本排序,冒泡排序,快速排序,插入排序,非常实用,有兴趣的同学快来看看吧。 代码如下复制代码classbevin{public$pub...2017-07-06- 这篇文章主要介绍了Java排序算法三之归并排序的递归与非递归的实现示例解析,文章通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-08-05
- 这篇文章主要介绍了php排序算法,结合实例形式分析了php数据查询、排序、数组去重、遍历与排序的相关操作技巧与注意事项,需要的朋友可以参考下...2016-10-20
- 这篇文章主要介绍了c语言实现奇偶排序算法,有需要的朋友可以参考一下...2020-04-25
- 这篇文章主要介绍了算法之排序算法的算法思想和使用场景总结,本文讲解了插入排序、交换排序、选择排序等几大类排序算法的特点、思想和使用场景,需要的朋友可以参考下...2020-04-25
- 一个快速排序算法代码一个快速排序算法代码,代码内有注释,大家参考使用吧...2020-04-25
- 这篇文章主要介绍了7种排序算法的实现示例,需要的朋友可以参考下...2020-04-25
- 本教程我们用PHP实例来讲解冒泡排序法,快速排序法,选择排序法,插入排序法等四大基础排序算法,我们的重点是给出算法思路,这种思路同样适用于其他编程语言。 四大基本排...2016-11-25
- php 常用的排序算法代码[冒泡,递归排序 冒泡排序算法 function bubblesort($arr) { $n=count($arr); for($i=0;$i<$n;$i++) { for($j=$i;$j<=$n-1;$j++) { if(...2016-11-25
- 这篇文章主要介绍了C语言基本排序算法之插入排序与直接选择排序实现方法,结合具体实例形式分析了插入排序与直接选择排序的定义、使用方法及相关注意事项,需要的朋友可以参考下...2020-04-25