#include<iostream>
using namespace std;
template<class T>
void mySwap(T& a, T& b)
{
T temp = a;
a = b;
b = temp;
}
//冒泡
void BubbleSort(int arr[], int length)
{
for (size_t i =0; i < length; i++)
{
for (size_t j = 0; j < length-i-1; j++)
{
if (arr[j] < arr[j + 1])
{
mySwap(arr[j], arr[j + 1]);
}
}
}
}
//选择
void ChoiceSort(int arr[], int length)
{
/*
第一次从待排序的数据元素中选出最小（或最大）的一个元素，
存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，
然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
*/
for (size_t i = 0; i < length; i++)
{
int max = i;
for (size_t j = i; j < length; j++)
{
if (arr[j] < arr[j + 1])
{
max = j+1;
}
}
if (max != i)
{
mySwap(arr[max], arr[i]);
}
}
}
//快速排序
void QuickSort(int arr[], int head, int end)
{
if (arr == NULL)
{
return;
}
if (head >= end)
{
return;
}
int i = head;
int j = end;
int refValue = arr[i];
//从小到大
while (i<j)
{
while (i < j && refValue < arr[j])
{
j--;
}
//交换arr[j]-->arr[i]
arr[i] = arr[j];
while (i < j && refValue > arr[i])
{
i++;
}
arr[j] = arr[i];
}
//中间值赋值
int mid = i;
arr[mid] = refValue;
//递归
QuickSort(arr, head, mid-1);
QuickSort(arr, mid + 1, end);
}
template <class T>
void myPrint(T arr[], int length)
{
for (size_t i = 0; i < length; i++)
{
cout << arr[i] << ' ';
}
cout << endl;
}
int main()
{
int arr[] = {0,1,2,3,4,5,6,7,8,9 };
int length = sizeof(arr) / sizeof(int);
cout << "------冒泡------" << endl;
BubbleSort(arr, length);
myPrint(arr, length);
int brr[] = { 0,1,2,3,4,5,6,7,8,9 };
cout << "------选择------" << endl;
ChoiceSort(brr, length);
myPrint(brr, length);
cout << "------快排------" << endl;
QuickSort(brr, 0,length-1);
myPrint(brr, length);
return 0;
}
