常用排序算法整理分享(快速排序算法、希尔排序)

//一些排序算法整理
//插入排序算法
//直接插入排序
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;
}