快速排序作业的总结，因为要看动漫所以写的很草率

QuickSort

vector

元素交换

swap(vector[i]，vector[j])

遍历方式

for(auto i : num)
	cout << i << endl;

ctime

CLOCKS_PER_SEC, 它用来表示一秒钟会有多少个时钟计时单元。

#include <ctime>
clock_t startTime, endTime;
startTime = clock();
endTime = clock();

三点取中

/**
 * @file QuickSort.h
 * @author 鲁硕 (3200101874@zju.edu.cn)
 * @date 2021-12-15
 * 
 * @brief QuickSort的实现
 * 
 */
#include <iostream>
#include <vector>
using namespace std;
#define MAX_LENGTH 10

/**
 * @brief 三数取中选择
 * 
 * @tparam Compareble 
 * @param a 
 * @param left 
 * @param right 
 * @return Compareble 
 */
template <typename Compareble>
Compareble medianPivot(std::vector<Compareble>& a,int left,int right)
{
  int center = (left + right) / 2;
  if(a[center] < a [left])
    swap(a[left], a[center]);
  if(a[right] < a [left])
    swap(a[left], a[right]);
  if(a[right] < a [center])
    swap(a[center], a[right]);

  swap(a[center], a[right - 1]);
  return a[right - 1];
#rand swap(i, right)
return a[right]
}



template <typename Compareble>
int mediansort(std::vector<Compareble>& items,int left,int right)
{
  if(right - left + 1 > MAX_LENGTH)
    {

      int i = left;#rand left-1
      int j = right -1;#rand right
      const Compareble & pivot = medianPivot(items, left, right);

      while(true)
	{
	  while (items[++i] < pivot)
	  {}
	  while (items[--j] > pivot)
	  {}
	  if (i < j)
	    swap(items[i], items[j]);
	  else
	    break;
	}
      swap(items[i], items[right - 1]);#rand i,right

      mediansort(items, left, i - 1);#rand left，i-1
      mediansort(items, i + 1, right);#rand i+1 right
    }
  else
    insertSort(items, left, right);
}



template <typename Compareble>
void medianSort(std::vector<Compareble>& items)
{
  mediansort(items, 0, items.size() - 1);
}

经过该算法可以使得left center right 的大小按小到大重排。取center为Pivot

left <= Pivot <= right

接下来只需分析left+1 — right-1

又center与right-1 互换

接下来只需分析left+1 — right-2

排序后将大于pivot的最小值i与right-1呼唤，那么这时i对应的就是pivot,接着分析sort(left，i - 1) sort(i+1, right)

随机法