C语言常用排序算法集合

#include 
#include 
#include 
#include 
//选择排序
long selectSort(int* arr, int length)
{
    struct timeval time1, time2;
    gettimeofday(&time1, NULL);
    for (int i = 0; i < length - 1; i++)
    {
 for (int j = i + 1; j < length; j++)
 {
     if (arr[i] > arr[j])
     {
  arr[i] = arr[i] ^ arr[j];
  arr[j] = arr[i] ^ arr[j];
  arr[i] = arr[i] ^ arr[j];
     }
 }
    }
    gettimeofday(&time2, NULL);
    return time2.tv_sec - time1.tv_sec;
}
//插入排序
long insertSort(int* arr, int length)
{
    struct timeval time1, time2;
    gettimeofday(&time1, NULL);
    for (int i = 1; i < length; i++)
    {
 if (arr[i] < arr[i - 1])
 {
     for (int j = 0; j < i; j++)
     {
  if (arr[i] < arr[j])
  {
      arr[i] = arr[i] ^ arr[j];
      arr[j] = arr[i] ^ arr[j];
      arr[i] = arr[i] ^ arr[j];
  }
     }
 }
    }
    gettimeofday(&time2, NULL);
    return time2.tv_sec - time1.tv_sec;
}
//折半插入排序
long binaryInsertSort(int* arr, int length)
{
    struct timeval time1, time2;
    gettimeofday(&time1, NULL);
    int head, tail, mid;
    for (int i = 1; i < length; i++)
    {
 if (arr[i] < arr[i - 1])
 {
     head = 0;
     tail = i - 1;
     while (head <= tail)
     {
  mid = (head + tail) / 2;
  if (arr[i] < arr[mid])
  {
      tail = mid - 1;
      continue;
  }
  if (arr[i] > arr[mid])
  {
      head = mid + 1;
  }
  if (arr[i] == arr[mid])
  {
      head = mid;
      break;
  }
     }
     for (int k = i; k > head; k--)
     {
  arr[k] = arr[k] ^ arr[k - 1];
  arr[k - 1] = arr[k] ^ arr[k - 1];
  arr[k] = arr[k] ^ arr[k - 1];
     }
 }
    }
    gettimeofday(&time2, NULL);
    return time2.tv_sec - time1.tv_sec;
}
//希尔排序内部替换
void shellReplace(int* arr, int length, int interval)
{
    int i = 0, j;
    while (i + interval <= length - 1)
    {
 if (arr[i] > arr[i + interval])
 {
     arr[i] = arr[i] ^ arr[i + interval];
     arr[i + interval] = arr[i] ^ arr[i + interval];
     arr[i] = arr[i] ^ arr[i + interval];
     j = i;
     while (j - interval >= 0)
     {
  if (arr[j] < arr[j - interval])
  {
      arr[j] = arr[j] ^ arr[j - interval];
      arr[j - interval] = arr[j] ^ arr[j - interval];
      arr[j] = arr[j] ^ arr[j - interval];
      j -= interval;
  }
  else
  {
      break;
  }
     }
 }
 i++;
    }
}
//希尔排序
long shellSort(int* arr, int length)
{
    struct timeval time1, time2;
    gettimeofday(&time1, NULL);
    int interval = length >> 1;
    while (interval > 0)
    {
 shellReplace(arr, length, interval);
 interval >>= 1;
    }
    gettimeofday(&time2, NULL);
    return time2.tv_sec - time1.tv_sec;
}
void quickSortDetail(int* arr, int start, int end)
{
    if (start < end)
    {
 int left = start;
 int right = end;
 int store = arr[end];
 while (left < right)
 {
     while (arr[left] <= store && left != right)
     {
  left++;
     }
     if (left != right)
     {
  arr[right] = arr[left];
     }
     while (arr[right] > store && left != right)
     {
  right--;
     }
     if (left != right)
     {
  arr[left] = arr[right];
     }
 }
 arr[left] = store;
 quickSortDetail(arr, start, left - 1);
 quickSortDetail(arr, left + 1, end);
    }
}
//快速排序
long quickSort(int* arr, int length)
{
    struct timeval time1, time2;
    gettimeofday(&time1, NULL);
    quickSortDetail(arr, 0, length - 1);
    gettimeofday(&time2, NULL);
    return time2.tv_sec - time1.tv_sec;
}
//冒泡排序
long bubbleSort(int* arr, int length)
{
    struct timeval time1, time2;
    gettimeofday(&time1, NULL);
    for (int i = length - 1; i > 0; i--)
    {
 for (int j = 0; j < i; j++)
 {
     if (arr[j] > arr[j + 1])
     {
  arr[j] = arr[j] ^ arr[j + 1];
  arr[j + 1] = arr[j] ^ arr[j + 1];
  arr[j] = arr[j] ^ arr[j + 1];
     }
 }
    }
    gettimeofday(&time2, NULL);
    return time2.tv_sec - time1.tv_sec;
}
void buildHeap(int* arr, int end)
{
    struct timeval time1, time2;
    gettimeofday(&time1, NULL);
    int nodeChild = end >> 1;
    int* max;
    for (int i = nodeChild - 1; i >= 0; i--)
    {
 if ((i << 1) + 2 >= end)
 {
     if (arr[(i << 1) + 1] > arr[i])
     {
  arr[i] = arr[i] ^ arr[(i << 1) + 1];
  arr[(i << 1) + 1] = arr[i] ^ arr[(i << 1) + 1];
  arr[i] = arr[i] ^ arr[(i << 1) + 1];
     }
 }
 else
 {
     max = arr[(i << 1) + 1] > arr[(i << 1) + 2] ? &arr[(i << 1) + 1] : &arr[(i << 1) + 2];
     if (*max > arr[i])
     {
  arr[i] = arr[i] ^ *max;
  *max = arr[i] ^ *max;
  arr[i] = arr[i] ^ *max;
     }
 }
    }
}
//堆排序
long heapSort(int* arr, int length)
{
    struct timeval time1, time2;
    gettimeofday(&time1, NULL);
    int i = length;
    while (i > 1)
    {
 buildHeap(arr, i);
 arr[0] = arr[0] ^ arr[i - 1];
 arr[i - 1] = arr[0] ^ arr[i - 1];
 arr[0] = arr[0] ^ arr[i - 1];
 i--;
    }
    gettimeofday(&time2, NULL);
    return time2.tv_sec - time1.tv_sec;
}
//归并排序(由于该算法比较复杂，将详细注释)
long mergerSort(int* arr, int length)
{
    //定义时间结构体
    struct timeval time1, time2;
    //获取当前时间
    gettimeofday(&time1, NULL);
    //申请一块与待排序的数组相同大小的空间
    int* copy = (int*)malloc(sizeof(int) * length);
    //定义原数组和新建数组交换标识变量，默认从原数组开始
    int isArr = 1;
    //定义每一组的元素个数，之所以为double是为了下面的ceil函数做准备
    double groupNum = 1;
    //定义变量，i为循环变量，start为跟随数组索引变量，index为每一次数组复制时的位置记录变量，
    // groupA是分组一的索引记录变量
    //groupB为分组二的索引记录变量，groupBinary表示有几对分组进行归并
    int i, start, index, groupA, groupB, groupBinary;
    //groupCount计算出分组的数量
    int groupCount = (int)ceil(length / groupNum);
    //判断，当分组数量大于1时进行循环，为1时也自然就不用循环了，因为都已经排好序了
    while (groupCount > 1)
    {
 //计算出分组对数
 groupBinary = groupCount / 2;
 //赋start为0
 start = 0;
 //赋index为0
 index = 0;
 //总共肯定只能进行groupBinary对分组的归并，分布上组的肯定也只有一个，放在下一次的比较中
 for (i = 0; i < groupBinary; i ++)
 {
     //每一对分组归并，从数组的start位置开始
     groupA = start;
     //这一对分组中的第二组从start位置偏移groupNum个位置开始，因为每一对分组总是组里元素数量的两倍
     groupB = start + (int)groupNum;
     //循环对一对分组进行归并，原理是，那个小，那个先往待放入数组走
     while (groupA < start + groupNum && groupB < start + 2 * groupNum && groupB < length)
     {
  //由于是两个数组交替赋值，所以isArr就是区分它们的
  if (isArr == 1)
  {
      //如果第一组比后一组的元素小，则优先进入，因为是升序排列嘛
      if (arr[groupA] < arr[groupB])
      {
   copy[index] = arr[groupA];
   index ++;
   groupA ++;
      }
      else
      {
   copy[index] = arr[groupB];
   index ++;
   groupB ++;
      }
  }
  else
  {
      if (copy[groupA] < copy[groupB])
      {
   arr[index] = copy[groupA];
   index ++;
   groupA ++;
      }
      else
      {
   arr[index] = copy[groupB];
   index ++;
   groupB ++;
      }
  }
     }
     //当某一个分组没有元素以后，剩下的那个分组要是有元素，就依次把所有剩下的元素塞进去
     while (groupA < start + groupNum)
     {
  if (isArr == 1)
  {
      copy[index] = arr[groupA];
      index ++;
      groupA ++;
  }
  else
  {
      arr[index] = copy[groupA];
      index ++;
      groupA ++;
  }
     }
     while (groupB < start + 2 * groupNum && groupB < length)
     {
  if (isArr == 1)
  {
      copy[index] = arr[groupB];
      index ++;
      groupB ++;
  }
  else
  {
      arr[index] = copy[groupB];
      index ++;
      groupB ++;
  }
     }
     start += 2 * groupNum;
 }
 if (isArr == 1)
 {
     //由于有没有参与归并的分组，所以就把这些被暂时遗弃的分组再移到当前活动数组
     while (index < length)
     {
  copy[index] = arr[index];
  index ++;
     }
     isArr = 0;
 }
 else
 {
     while (index < length)
     {
  arr[index] = copy[index];
  index ++;
     }
     isArr = 1;
 }
 groupNum *= 2;
 groupCount = (int)ceil(length / groupNum);
    }
    //如果排完序，这个活跃数组不恰好是arr，那么就是讲copy数组的值一个个的赋过去
    if (isArr == 0)
    {
 for (i = 0; i < length; i++)
 {
     arr[i] = copy[i];
 }
    }
    //回收备用数组copy，以免造成内存浪费
    free(copy);
    //获取排完序当前时间
    gettimeofday(&time2, NULL);
    //返回时间差
    return time2.tv_sec - time1.tv_sec;
}
void printArr(int* arr, int length)
{
    for (int i = 0; i < length; i++)
    {
 printf("%d t", arr[i]);
    }
    printf("n");
}
int main(int argc, char** argv)
{
    srand(time(NULL));
    int* arr = (int*)malloc(sizeof(int) * 50000);
    for (int i = 0; i < 50000; i++)
    {
 arr[i] = rand();
    }
    printf("Select sort use time: %ld n", selectSort(arr, 50000));
    for (int i = 0; i < 50000; i++) {
 arr[i] = rand();
    }
    printf("Insert sort use time: %ld n", insertSort(arr, 50000));
    for (int i = 0; i < 50000; i++) {
 arr[i] = rand();
    }
    printf("Binary insert sort use time: %ld n", binaryInsertSort(arr, 50000));
    for (int i = 0; i < 50000; i++) {
 arr[i] = rand();
    }
    printf("Shell sort use time: %ld n", shellSort(arr, 50000));
    for (int i = 0; i < 50000; i++) {
 arr[i] = rand();
    }
    printf("Quick sort use time: %ld n", quickSort(arr, 50000));
    for (int i = 0; i < 50000; i++) {
 arr[i] = rand();
    }
    printf("Bubble sort use time: %ld n", bubbleSort(arr, 50000));
    for (int i = 0; i < 50000; i++) {
 arr[i] = rand();
    }
    printf("Heap sort use time: %ld n", heapSort(arr, 50000));
    for (int i = 0; i < 50000; i++) {
 arr[i] = rand();
    }
    printf("Merger sort use time: %ld n", mergerSort(arr, 50000));
    free(arr);
    return 0;
}