{

int temp =arr[i];

arr[i] = arr[j] ;

arr[j] = temp ;

// arr[i] = arr[i] ^ arr[j];

// arr[j] = arr[i] ^ arr[j];

// arr[i] = arr[i] ^ arr[j];

{

arr2 =arr;

std::sort(arr2.begin(),arr2.end());

{

cout<<__FUNCTION__<<endl;

for(auto i:arr){

cout<< i<<" ";

}

cout<<endl;

cout<<endl;

{

arr.resize(size);

srand(time(0));

for(int i=0;i<size ;i++){

arr[i] = (rand())% (maxValue -minValue +1) +minValue;

}

{

if(arr.size() !=arr2.size()){

return false;

}else{

for(int i=0;i<arr.size();i++){

if(arr[i] != arr2[i]){

return false;

}

}

return true;

}

{

cout<<__FUNCTION__<<endl;

if(arr.size() <2){

return ;

}

bool hasSorted = false; //有序

// 1 ?比较相邻的元素。如果第一个比第二个大，就交换它们两个；

// 2 ?对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，

// 这样在最后的元素应该会是最大的数；

// 3 ?针对所有的元素重复以上的步骤，除了最后一个；

// 4 ?重复步骤1~3，直到排序完成。

// 原始

// 38 50 53 83 36 30 21 97

// BubbleSort

// 97 1

// 83 97 2

// 53 83 97 3

// 50 53 83 97 4

// 36 38 50 53 83 97 5

// 21 30 36 38 50 53 83 97 6 OK

for (int end = arr.size() - 1; end > 0 && (!hasSorted); end--) {

hasSorted =true;

for (int i = 0; i < end; i++) {

if (arr[i] > arr[i + 1]) {

swap(arr, i, i + 1);

hasSorted = false;

}

}

// if(hasSorted)

// return;

}

{

// cout<<__FUNCTION__<<endl;

if(arr.size() <2){

return ;

}

// i是第几次对比的数据，i-1是之前有序的数据

// ..... 5 3 4 8 9

// ..... i-1 i——————————-——》 i待插入的数据

// ..... i-1 i

// ..... j j=[i-1]是

// 26 3 79 99 86 77 0 10

//

// 3 26

// 3 26 79

// 3 26 79 99

// 3 26 79 86 99

// 3 26 77 79 86 99

// 0 3 26 77 79 86 99

// 0 3 10 26 77 79 86 99

// ?从第一个元素开始，该元素可以认为已经被排序；

// ?取出下一个元素，在已经排序的元素序列中从后向前扫描；

// ?如果该元素（已排序）大于新元素，将该元素移到下一位置；

// ?重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

// ?将新元素插入到该位置后；

// ?重复步骤2~5。

#if 1

for (int i = 1; i < arr.size(); i++) {

#if 0

int j = i - 1;

for (; j >= 0 && arr[j] > arr[j + 1]; j--) {

swap(arr, j, j + 1);

}

#else

// 优化版本 ERR

int temp = arr[i];

int newPos = i-1;

/* i 之前的元素都是有序的，找到比temp小的插入到他后面，

for (; newPos >= 0 && arr[newPos] > temp; newPos--) {

arr[newPos+1] = arr[newPos];

}

arr[newPos+1] = temp;

for(auto i:arr){

cout<<i<<" ";

}

cout<<endl;

#endif

}

#endif

{

cout<<__FUNCTION__<<endl;

if(arr.size() <2){

return ;

}

// ?初始状态：无序区为R[1..n]，有序区为空；

// ?第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。

// 该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，

// 使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；

// ?n-1趟结束，数组有序化了。

// printf

// 2 32 42 45 29 72 52 74

// selectionSort

// 2 32 42 45 29 72 52 74

// 2 29 42 45 32 72 52 74

// 2 29 32 45 42 72 52 74

// 2 29 32 42 45 72 52 74

// 2 29 32 42 45 72 52 74

// 2 29 32 42 45 52 72 74

// 2 29 32 42 45 52 72 74

// result :1

for (int i = 0; i < arr.size() - 1; i++) {

int minIndex = i; //从第A[i=0]个数据开始，，并且排序后将值放在minIndex位置

// 每次选择一个待排序 [i+1]...>的数据最小值

for (int j = i + 1; j < arr.size(); j++) {

minIndex = arr[j] < arr[minIndex] ? j : minIndex;

}

swap(arr, i, minIndex);

}

{

// ?将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；

// ?将堆顶元素R[1]与最后一个元素R[n]交换，

// 此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),

// 且满足R[1,2…n-1]<=R[n]；

// ?由于交换后新的堆顶R[1]可能违反堆的性质，

// 因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，

// 然后再次将R[1]与无序区最后一个元素交换，

// 得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。

// 不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

cout<<__FUNCTION__<<endl;

if(arr.size() <2){

return ;

}

for (int i = 0; i < arr.size() ; i++) {

heapInsert(arr, i); //逐个插入数据 尾部 arr[0]是大顶堆。

}

int size = arr.size() ;

swap(arr, 0, --size); //大顶堆，把上一次的大堆顶，放在arr[size-1];

//对大顶堆，arr[0] <----> arr[size-1]进行堆调整;

while (size > 0) {

heapify(arr, 0, size);

swap(arr, 0, --size);

}

{

// 节点值>父节点，交换

while (arr[index] > arr[(index - 1) / 2]) {

swap(arr, index, (index - 1) / 2);

index = (index - 1) / 2; //节点的父亲

}

{

int left = index * 2 + 1;

while (left < size) {

int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;

largest = arr[largest] > arr[index] ? largest : index;

if (largest == index) {

break;

}

swap(arr, largest, index);

index = largest;

left = index * 2 + 1;

}

{

if (arr.size() < 2) {

return;

}

quickSort(arr, 0, arr.size() - 1);

{

// ?从数列中挑出一个元素，称为 “基准”（pivot）；

// ?重新排序数列，所有元素比基准值小的摆放在基准前面，

// 所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。

// 在这个分区退出之后，该基准就处于数列的中间位置。

// 这个称为分区（partition）操作；

// ?递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

if (l < r) {

int p = partition(arr, l, r);

quickSort(arr, l, p - 1);

quickSort(arr, p, r);

}

{

int less = l - 1;

int more = r;

while (l < more) {

if (arr[l] < arr[r]) {

swap(arr, ++less, l++);

} else if (arr[l] > arr[r]) {

swap(arr, --more, l);

} else {

l++;

}

}

swap(arr, more, r);

return l;

{

if (l == r) {

return;

}

int mid = l + ((r - l) >> 1);

mergeSort(arr, l, mid);

mergeSort(arr, mid + 1, r);

merge(arr, l, mid, r);

{

if (arr.size() < 2) {

return;

}

mergeSort(arr, 0, arr.size() - 1);

{

// 将已有序的子序列合并，得到完全有序的序列；

// 即先使每个子序列有序，再使子序列段间有序。

// 若将两个有序表合并成一个有序表，称为2-路归并。

// ?把长度为n的输入序列分成两个长度为n/2的子序列；

// ?对这两个子序列分别采用归并排序；

// ?将两个排序好的子序列合并成一个最终的排序序列。

vector<int> help(r - l + 1 , 0);

int i = 0;

int p1 = l;

int p2 = m + 1;

while (p1 <= m && p2 <= r) {

help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];

}

while (p1 <= m) {

help[i++] = arr[p1++];

}

while (p2 <= r) {

help[i++] = arr[p2++];

}

for (i = 0; i < help.size(); i++) {

arr[l + i] = help[i];

}

{

cout<<__FUNCTION__<<endl;

// ?找出待排序的数组中最大和最小的元素；

// ?统计数组中每个值为i的元素出现的次数，存入数组C的第i项；

// ?对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；

// ?反向填充目标数组：将每个元素i放在新数组的第C(i)项，

// 每放一个元素就将C(i)减去1。

// only for 0~200 value

if ( arr.size() < 2) {

return;

}

int max = INT32_MIN;

for (int i = 0; i < arr.size() ; i++) {

max = std::max(max, arr[i]);

}

vector<int> bucket(max + 1 , 0);

for (int i = 0; i < arr.size(); i++) {

bucket[arr[i]]++;

}

int i = 0;

for (int j = 0; j < bucket.size(); j++) {

while (bucket[j]-- > 0) {

arr[i++] = j;

}

}

{

cout<<__FUNCTION__<<endl;

// ?设置一个定量的数组当作空桶；

// ?遍历输入数据，并且把数据一个一个放到对应的桶里去；

// ?对每个不是空的桶进行排序；

// ?从不是空的桶里把排好序的数据拼接起来。

// only for 0~200 value

if ( arr.size() < 2) {

return;

}

int max = INT32_MIN;

for (int i = 0; i < arr.size() ; i++) {

max = std::max(max, arr[i]);

}

vector<int> bucket(max + 1 , 0);

for (int i = 0; i < arr.size(); i++) {

bucket[arr[i]]++;

}

int i = 0;

for (int j = 0; j < bucket.size(); j++) {

while (bucket[j]-- > 0) {

arr[i++] = j;

}

}

{

int max = INT32_MIN;

for (int i = 0; i < arr.size(); i++) {

max = std::max(max, arr[i]);

}

int res = 0;

while (max != 0) {

res++;

max /= 10;

}

return res;

{

volatile int radix = 10;

int i = 0, j = 0;

// int[] count = new int[radix];

// int[] bucket = new int[end - begin + 1];

// ?取得数组中的最大数，并取得位数；

// ?arr为原始数组，从最低位开始取每个位组成radix数组；

// ?对radix进行计数排序（利用计数排序适用于小范围数的特点）；

vector<int> count(radix);

vector<int> bucket(end - begin + 1);

for (int d = 1; d <= digit; d++) {

for (i = 0; i < radix; i++) {

count[i] = 0;

}

for (i = begin; i <= end; i++) {

j = getDigit(arr[i], d);

count[j]++;

}

for (i = 1; i < radix; i++) {

count[i] = count[i] + count[i - 1];

}

for (i = end; i >= begin; i--) {

j = getDigit(arr[i], d);

bucket[count[j] - 1] = arr[i];

count[j]--;

}

for (i = begin, j = 0; i <= end; i++, j++) {

arr[i] = bucket[j];

}

}

{

if ( arr.size() < 2) {

return;

}

radixSort(arr, 0, arr.size() - 1, maxbits(arr));

{

// ?选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

// ?按增量序列个数k，对序列进行k 趟排序；

// ?每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，

// 分别对各子表进行直接插入排序。仅增量因子为1 时，

// 整个序列作为一个表来处理，表长度即为整个序列的长度。

int gap = arr.size()/2; //步长默认

while(gap > 0){

int beg = gap -1; //开始比较的位置，一半的前一个数据开始往前

while(beg >= 0 ){

shellInsert(arr,beg,gap);

beg--;

}

gap = gap / 2;

}

{

for (int i = beg+gap; i < arr.size(); i+=gap) {

#if 0

int j = i - gap;

for (; j >= 0 && arr[j] > arr[j + gap]; j-=gap) {

swap(arr, j, j + gap);

}

#else

// 优化版本 ERR

int temp = arr[i];

int newPos = i-gap;

for (; newPos >= 0 && arr[newPos] > temp; newPos-=gap) {

arr[newPos+gap] = arr[newPos];

}

arr[newPos+gap] = temp;

#endif

}