MT5(C++)软件编程-快速排序算法

1. MT5(C++)软件编程十大排序算法 - 冒泡排序算法 (bubble Sort)
2. MT5(C++)软件编程十大排序算法 - 选择排序算法 (select Sort)
3. MT5(C++)软件编程十大排序算法 - 插入排序算法 (insert Sort)
4. MT5(C++)软件编程十大排序算法 - 快速排序算法 (quick Sort)
5. MT5(C++)软件编程十大排序算法 - 希尔排序算法 (shell Sort)
6. MT5(C++)软件编程十大排序算法 - 堆排序算法 (heap Sort)
7. MT5(C++)软件编程十大排序算法 - 归并排序算法 (merge Sort)
8. MT5(C++)软件编程十大排序算法 - 计数排序算法 (counting Sort)
9. MT5(C++)软件编程十大排序算法 - 桶排序算法 (bucket Sort)
10. MT5(C++)软件编程十大排序算法 - 基数排序算法 (radix Sort)

1 快速排序算法
以一个基数为标准, 从左边 和右边合拢排序
arr: 需要排序的数组
seq: 排序的方向, true 为升序, false为降序

template <typename T1>
void quickSort(T1 &arr[], const bool seq = true)
{
  int len = ArraySize(arr);
  _partition(arr,0,len - 1,seq);
  
  
  
}

template <typename T>
void _partition(T &arr[], int l, int r,bool seq = true)
{
  if (l >= r) return;
  int index = l + 1;
  if(seq)
  {
    
    int key = arr[l];
    int low = l;
    int high = r;
    
    while(l<r)
    {
      while(l<r && arr[r] >= key)r--;
      arr[l] = arr[r];
      while(l<r && arr[l] <= key)l++;
      arr[r] = arr[l];
    }
    arr[r] = key;
    _partition(arr,low,l - 1,seq);
    _partition(arr,l + 1,high,seq);
    
  }
  else
  {
    int key = arr[l];
    int low = l;
    int high = r;
    
    while(l<r)
    {
      while(l<r && arr[r] < key)r--;
      arr[l] = arr[r];
      while(l<r && arr[l] > key)l++;
      arr[r] = arr[l];
    }
    arr[r] = key;
    _partition(arr,low,l - 1,seq);
    _partition(arr,l + 1,high,seq);
  }
  
}

template <typename T>
void _quickSortInternal(T & arr[], int l, int r, bool seq = true)
{
  if(l > r) return;
  int p = _partition(arr,l,r,seq);
  _quickSortInternal(arr,l,p - 1,seq);
  _quickSortInternal(arr,p + 1,r,seq);
}

2二路快速排序算法
以一个基数为标准, 从左边 和右边合拢排序
arr: 需要排序的数组
seq: 排序的方向, true 为升序, false为降序

template <typename T1>
void quickSort2(T1 &arr[], const bool seq = true)
{
    int size = ArraySize(arr);
    _quickSortInternal2(arr,0,size - 1,seq);

}

template <typename T>
int _partition2(T &arr[], int l, int r,bool seq = true)
{
  int temp = arr[l];
  int i = l + 1;
  int j = r;
  if(seq)
  while(true)
  {
    while(i<=j && arr[i] < temp) i++;
    while(i<=j && arr[j] > temp) j--;
    if(i>=j) break;
    swap(arr[i],arr[j]);
    i++; j--;
    return j;
  }
  else
  {
    while(true)
    {
      while(i<=j && arr[i] > temp) i++;
      while(i<=j && arr[j] < temp) j--;
      if(i>=j) break;
      swap(arr[i],arr[j]);
      i++; j--;
      return j;
    }
  }
  swap(arr[l],arr[j]);
  return j;
}


template <typename T>
void _quickSortInternal2(T & arr[], int l, int r, bool seq = true)
{
  if(l > r) return;
  int p = _partition2(arr,l,r,seq);
  _quickSortInternal2(arr,l,p - 1,seq);
  _quickSortInternal2(arr,p + 1,r,seq);
}

3 三路快速排序算法
以一个基数为标准, 从左边 和右边合拢排序
arr: 需要排序的数组
seq: 排序的方向, true 为升序, false为降序

template <typename T1>
void quickSort3(T1 &arr[], const bool seq = true)
{
    int size = ArraySize(arr);
    _quickSortInternal3(arr,0,size - 1,seq);

}

template <typename T>
int _partition3(T &arr[], int l, int r,bool seq = true)
{
  int temp = arr[l];
  int i = l + 1;
  int j = r;
  if(seq)
  while(true)
  {
    while(i<=j && arr[i] < temp) i++;
    while(i<=j && arr[j] > temp) j--;
    if(i>=j) break;
    swap(arr[i],arr[j]);
    i++; j--;
    return j;
  }
  else
  {
    while(true)
    {
      while(i<=j && arr[i] > temp) i++;
      while(i<=j && arr[j] < temp) j--;
      if(i>=j) break;
      swap(arr[i],arr[j]);
      i++; j--;
      return j;
    }
  }
  swap(arr[l],arr[j]);
  return j;
}


template <typename T>
void _quickSortInternal3(T & arr[], int l, int r, bool seq = true)
{
  if(l > r) return;
  int temp = arr[l];
  int lt = l;
  int i =lt + 1;
  int gt = r + 1;
  if(seq)
  {
    while(i < gt)
    {
      if(arr[i] < temp)
      {
        swap(arr[i],arr[lt + 1]);
        i++; lt++;
      }
      else if (arr[i] > temp)
      {
        swap(arr[i],arr);
        gt--;
      }
      else i++;
    }
    swap(arr[l],arr[lt]);
    _quickSortInternal3(arr,l,lt - 1,seq);
    _quickSortInternal3(arr,gt,r,seq);
  }
  else
  {
    while(i < gt)
    {
      if(arr[i] > temp)
      {
        swap(arr[i],arr[lt + 1]);
        i++; lt++;
      }
      else if (arr[i] < temp)
      {
        swap(arr[i],arr);
        gt--;
      }
      else i++;
    }
    swap(arr[l],arr[lt]);
    _quickSortInternal3(arr,l,lt - 1,seq);
    _quickSortInternal3(arr,gt,r,seq);
  }
}