#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)
{
 //思路：最后一個(gè)依次和前面的進(jìn)行比較
 //將滿足的條件的往后移動，當(dāng)然是從頭
 //開始且是從最小比較數(shù)組開始逐漸擴(kuò)大
 //到整個(gè)數(shù)組
 int i,j,temp;
 for(i = 1;i < len;++i) {
  //獲取最后一個(gè)索引數(shù)據(jù)
  temp = a[i];
  for(j = i - 1;j >= 0;--j) {
   //從倒數(shù)第二個(gè)開始
   if(a[j] > temp)//升序排列
    a[j + 1] = a[j];
   else
    break;//立刻退出
  }
  //將最后一個(gè)位置插入到合適的位置
  a[j + 1] = temp;
 }
}

//希爾排序
void
shell_insert_sort(int *a,int len)
{
 //思路：就是比直接插入排序多了層
 //循環(huán)，這層循環(huán)是用來控制步進(jìn)按
 //照算法的本來思路是這樣可以減少
 //交換次數(shù)
 int i,j,h,temp;
 for(h = len / 2;h > 0;h /= 2) {
  //內(nèi)層其實(shí)本質(zhì)還是直接插入
  //算法思路
  //注意下i += h和i++兩者對算
  //法的影響
  for(i = h;i < len;i += h) {
   //獲取最后一個(gè)索引的值
   temp = a[i];
   for(j = i - h;j >= 0;j -= h) {
    if(a[j] > temp)//升序排列
     a[j + h] = a[j];
    else
     break;
   }
   //將找到的位置插入最后一個(gè)索引
   a[j + h] = temp;
  }
 }
}

//選擇排序
//冒泡排序
void
bubble_swap_sort(int *a,int len)
{
 //思路：從數(shù)組最后開始兩兩比較
 //將底層滿足要求的數(shù)據(jù)逐漸交換
 //到上層，可能導(dǎo)致交換次數(shù)太多
 int i,j,temp;
 //如果一次冒泡中沒有發(fā)生交換可
 //以認(rèn)為此次排列已經(jīng)結(jié)束
 bool exchange = false;
 for(i = 0;i < len - 1;++i) {
  for(j = len - 1;j > i;--j) {
   //滿足條件的就進(jìn)行交換
   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)
{
 //思路：從數(shù)組中找一個(gè)值
 //然后排列數(shù)組使其兩邊要
 //么大于要么小于這個(gè)值，
 //然后遞歸下去排序
 //優(yōu)勢在于每次找中間值可
 //以交換很多次。
 int _low,_high,qivot;
 if(low < high) {
  _low = low;
  _high = high;
  //這里從最后一個(gè)開始
  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大的數(shù)據(jù)
   while(_low < _high && a[_low] < qivot)
    --_low;//逼近中間
   if(_low < _high)
    a[_high--] = a[_low];
  }
  //最后_low == _high那么這個(gè)位置就是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)
{
 //思路：就是遍歷數(shù)組找到極值
 //放到頭或者尾，這樣逐漸縮小
 //范圍到最小比較數(shù)組
 int i,j,pos,temp;
 for(i = 0;i < len - 1;++i) {
  //從頭開始獲取一個(gè)值假設(shè)為極值
  pos = i;
  for(j = i + 1;j < len;++j) {
   //滿足條件
   if(a[pos] > a[j])//升序
    pos = j;
  }
  if(pos != i) {
   //進(jìn)行交換
   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;
}