#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; }