常用排序算法

#include<stdio.h>

//冒泡算法
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void BubbleSort(int *arr, int length)
{
    for (int i = 0; i < length; i++)//O(n^2)
    {
        for (int j = 0; j+1 < length; j++)//O(n)相邻元素冒泡
        {
            if (arr[j] > arr[j + 1])
                swap(&arr[j], &arr[j+1]);
        }
    }
}

//选择排序法
void SelectionSort(int *arr, int length)
{
    for (int i = 0; i < length; i++)//O(n^2)
    {
        int min = arr[i];//赋初值，最小值
        int count = i;//记录最小值下标
        for (int j = i+1; j < length; j++)//选择最大的,O(n)
        {
            if (min > arr[j])
            {
                min = arr[j];//更新最小值
                count = j;//更新最小值下标
            }
        }
        swap(&arr[i], &arr[count]);//交换最小值
    }
}

//插入排序
void InsertSort(int *arr, int length)
{
    int temp;
    for (int i = 0; i < length; i++)//O(n^2)
    {
        temp = arr[i];
        int j = i;
        for (; j > 0 && temp < arr[j - 1];  j--)//如果满足向前挪位置，j--一直运行
        {
                arr[j] = arr[j - 1];
        }
        arr[j] = temp;//插入
    }
}

//快速排序
//int Partition(int *arr, int length, int start, int end)
//{
//  if (arr == NULL || length <= 0 || start < 0 || end <= 0 || end >= length)
//      return -1;
//  int base = arr[start];
//
//  int t_start = start;
//  int t_end = end;
//
//  
//
//  while (t_start < t_end && arr[t_start] < base)
//  {
//      --t_end;//向左移动
//      if (t_start < t_end)//什么时候交换
//      {
//          arr[t_start] = arr[t_end];
//          ++t_start;
//      }
//  }
//
//  while (t_start < t_end && arr[t_start] < base)
//  {
//      ++t_start;//向右移动
//      if (t_start < t_end)//什么时候交换
//      {
//          arr[t_end] = arr[t_start];
//          --t_end;
//      }
//  }
//  arr[t_start] = base;
//  return t_start;
//}
//
//void QuickSort(int* arr, int length, int start, int end)
//{
//  if (start == end)
//      return;
//  int index = Partition(arr, length, start, end);
//
//  if (index > start)
//      QuickSort(arr, length,start, index - 1);
//  if (index < end)
//      QuickSort(arr, length, index + 1, end);
//}



//int get_mid(int b[], int left, int right)
//{
//  int pivot = b[right];
//  while (left < right)
//  {
//      while (b[right] >= pivot && left < right) right--;
//      b[left] = b[right];
//      while (b[left] < pivot && left < right) left++;
//      b[right] = b[left];
//  }
//  b[left] = pivot;
//  return left;
//}
//void q_sort(int b[], int left, int right)
//{
//  if (left < right)
//  {
//      int mid = get_mid(b, left, right);
//      q_sort(b, left, mid - 1);
//      q_sort(b, mid + 1, right);
//  }
//       
//}
void quiksort(int a[], int low, int high)
{
    int left = low;//左边
    int right = high;//右边
    int temp = a[left];

    if (low < high)
    {
        while (left < right)
        {
            while ((a[right] >= temp) && (left < right))//右指针左移
            {
                right--;
            }
            a[left] = a[right];//赋值
            while ((a[left] <= temp) && (left < right))//左指针右移
            {
                left++;
            }
            a[right] = a[left];
        }
        a[left] = temp;
        quiksort(a, low, left - 1);
        quiksort(a, right + 1, high);
    }
    else
    {
        return;
    }
}
int main()
{
    int a[10] = { 1,9,5,3,4,2,6,8,7,0 };
    int length = sizeof(a) / sizeof(int);
    //BubbleSort(a, length);
    //SelectionSort(a, length);
    //InsertSort(a, length);
    //q_sort(a, 0, 9);
    quiksort(a, 0, 9);
    for (int i = 0; i < length; i++)
    {
        printf("%d\t", a[i]);
    }
    return 0;
}