題目描述： 給你一個(gè)整數(shù)數(shù)組 nums，將該數(shù)組升序排列。

上來(lái)的第一想法，居然就這么打卡成功了，哈哈哈哈哈哈哈哈

image

這個(gè)樣子是肯定不行滴，要進(jìn)步，就要自己親力親為，來(lái)，研究一下排序算法

image

插入排序： 簡(jiǎn)單插入排序 ----- 希爾排序 平均時(shí)間復(fù)雜由n2降低為n1.3，最壞時(shí)間復(fù)雜度，最好時(shí)間復(fù)雜度n2和空間復(fù)雜度o1均未變。

交換排序：冒泡排序 ------ 快速排序 平均時(shí)間復(fù)雜度由n2降低為nlogn，最壞時(shí)間復(fù)雜度由n2降低為nlogn，最好時(shí)間復(fù)雜度有損失，由n變?yōu)閚logn，空間復(fù)雜度有損失，由n變?yōu)閚logn

選擇排序：簡(jiǎn)單選擇排序 ----- 堆排序 平均時(shí)間復(fù)雜度又n2降低為nlogn，最壞時(shí)間復(fù)雜度由n2降低為nlogn，最好時(shí)間復(fù)雜度由n2降低為nlogn，空間復(fù)雜度是O1沒(méi)有變化

//
// Created by Xue,Lin on 2020/6/18.
//
#ifndef UNTITLED_SORT_ALGORITHM_H
#define UNTITLED_SORT_ALGORITHM_H
void swap(int &a, int &b)
{
   // cout << "break3" << endl;
   int tmp = a;
   a = b;
   b = tmp;
}
// 希爾排序是插入排序，堆排序是選擇排序，冒泡排序和快速排序是交換排序

// 1.插入排序  穩(wěn)定，不占用額外空間，平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度均為n2
// 思路為找到每個(gè)元素該在的位置，n輪循環(huán)后前n個(gè)元素有序，比較n+1元素和前n個(gè)元素
// 找到n+1元素應(yīng)在位置，插入，此時(shí)前n+1元素有序
// 兩輪循環(huán)
// 最壞時(shí)間復(fù)雜度n2，平均時(shí)間復(fù)雜度n2
// 最好情況為整個(gè)數(shù)組有序，每個(gè)元素僅需要和前一個(gè)元素比較，復(fù)雜度n
// 因此比較是個(gè)基本有序的數(shù)組
// 注意數(shù)組作為參數(shù)傳遞，一定要傳遞數(shù)組長(zhǎng)度，在函數(shù)內(nèi)無(wú)法判斷長(zhǎng)度
void insertSort(int a[10], int n)
{
   for(int i = 1; i < n; i++)
   {
       if (a[i] > a[i - 1])
       {
           continue;
       }
       for(int j = i - 1; j >= 0; j--)
       {
           if (a[j+1] < a[j])
           {
               swap(a[j+1], a[j]);
           } else
           {
               break;
           }
       }
   }
}

// 2.冒泡排序
// 注意是相鄰元素比較，如果想把最大的先撈出來(lái)，第二重循環(huán)就從前往后遍歷
// 如果是想把最小的先撈出來(lái)，第二重循環(huán)就從后往前遍歷
void bubbleSort(int a[], int n)
{
   for(int i = 0; i < n; i++)
   {
       for(int j = n; j >= i; j--)
       {
           if (a[j-1] > a[j])
           {
               swap(a[j-1], a[j]);
           }
       }
   }
}

// 3.快速排序，冒泡排序的升級(jí)，屬于交換排序類
// 快速排序基本思想為通過(guò)一趟排序?qū)⒋判虻挠涗浄指畛蓛蓚€(gè)獨(dú)立的部分
// 其中一部分記錄的關(guān)鍵字均比另外一部分要小，然后對(duì)這兩部分進(jìn)行分別排序
// 最終實(shí)現(xiàn)整個(gè)數(shù)組有序
// partition是快排的精髓部分，交換原始表a中數(shù)據(jù)位置，使小于樞紐值在左，大于樞紐值在右，最終返回樞紐所在位置
int partition(int a[], int low, int high)
{
   // 樞紐值設(shè)定為帶排序數(shù)組第一個(gè)元素
   // 由于樞紐值的選取會(huì)影響快排效率，有改進(jìn)法為3數(shù)選取，即在待排序數(shù)組中任選3個(gè)數(shù)，取中間數(shù)為樞紐
   int pivot_value = a[low];
   // 交換方式為low和high兩個(gè)指針移動(dòng)，
   // 先移動(dòng)high，high--，當(dāng)high小于pivot，交換，然后開(kāi)始low++，當(dāng)low大于pivot，交換
   // 再移動(dòng)high，重復(fù)上面過(guò)程，知道low和high相遇，代表此時(shí)partition結(jié)束
   while(low < high)
   {
       // cout << "low:" << low << " " << "high:" << high << endl;
       // 注意high要是有效的
       while(low < high && a[high] >= pivot_value)
       {
           high--;
       }
       swap(a[high], a[low]);
       // 注意這里要判斷l(xiāng)ow < high 并且 a[low] 小于等于而不是小于，不然遇到相等的會(huì)一直出不去
       while(low < high && a[low] <= pivot_value)
       {
           low++;
       }
       swap(a[low], a[high]);
   }
   return low;
}
void quickSort(int a[], int low, int high)
{
   if (low >= high)
   {
       return;
   }
   int pivot;
   pivot = partition(a, low, high);
   quickSort(a, low, pivot - 1);
   quickSort(a, pivot + 1, high);
}
void quickSort(int a[], int n)
{
   quickSort(a, 0, n - 1);
}

// 4.歸并排序
// 歸并排序的原理是假設(shè)原始序列包含n個(gè)記錄，可以看成是n個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度為1
// 然后兩兩歸并，得到【n/2】個(gè)長(zhǎng)度為2的子序列，再兩兩歸并，直到整個(gè)序列有序
void merge(int a[], int begin, int mid, int end)
{
   cout << "begin: " << begin << "end: " << end << endl;
   int *arr = new int(end-begin);
   // 將a中begin到end按照從小到大歸并到arr，其中【begin，mid），【mid，end）是兩個(gè)有序子序列
   int l1 = begin, l2 = mid;
   int index = 0;
   while(l1 < mid && l2 < end)
   {
       if (a[l1] < a[l2])
       {
           arr[index] = a[l1];
           l1++;
       } else{
           arr[index] = a[l2];
           l2++;
       }
       index++;
   }
   while(l1 < mid)
   {
       arr[index++] = a[l1++];
   }
   while(l2 < end)
   {
       arr[index++] = a[l2++];
   }
   for(int i = begin; i < end; i++)
   {
       a[i] = arr[i-begin];
   }
   return;
}
void msort(int a[], int begin, int end)
{
   if (begin >= end - 1)
   {
       return;
   }
   int mid = begin + (end - begin) / 2;
   cout << "begin: " << begin << "end: " << end << "mid:" << mid << endl;
   msort(a, begin, mid);
   msort(a, mid, end);
   merge(a, begin, mid, end);
   return;
}
void mergeSort(int a[], int n)
{
   msort(a, 0, n);
}

// 5.堆排序
// 堆是具有以下性質(zhì)的完全二叉樹(shù)：每個(gè)節(jié)點(diǎn)的值都大于或等于其左右孩子的節(jié)點(diǎn)值，稱為大頂堆
// 每個(gè)節(jié)點(diǎn)值都小于或等于其左右孩子的節(jié)點(diǎn)值，稱為小頂堆
// 堆排序就是利用堆進(jìn)行排序的方法。將待排序數(shù)組構(gòu)造成一個(gè)大頂堆，此時(shí)，這個(gè)序列的最大值就是堆頂
// 將他移走（就是把堆頂和堆數(shù)組末尾元素交換，此時(shí)末尾元素就是最大值）
// 然后將剩余n-1個(gè)序列重新構(gòu)造一個(gè)堆，這樣就會(huì)得到n個(gè)元素中次大值
// 反復(fù)重復(fù)，可以得到一個(gè)有序序列
// 所以核心是實(shí)現(xiàn)兩個(gè)函數(shù) 1.根據(jù)當(dāng)前序列構(gòu)建一個(gè)堆 2.在輸出堆頂元素后，如何調(diào)整剩余元素成為一個(gè)新堆
// 參考鏈接：https://www.cnblogs.com/wanglei5205/p/8733524.html
void headAdjust(int a[], int begin, int end)
{
   // 核心函數(shù)，建立堆
   // begin為第一個(gè)非葉子節(jié)點(diǎn)的下標(biāo)
   // cout << "begin:" << begin << "end:" << end << endl;
   int temp, j;
   temp = a[begin];
   for(j = 2*begin; j < end - 1; j=j*2)
   {
       // 找到一個(gè)比較大的元素和當(dāng)前元素進(jìn)行交換
       if (j < end - 1 && a[j] < a[j+1])
       {
           j++;
       }
       if (temp >= a[j])
       {
           break;
       }
       a[begin] = a[j];
       begin = j;
   }
   a[begin] = temp;
   // cout << "begin:" << begin << "end:" << end << endl;
   return;
}
void headSort(int a[], int n)
{
   int i;
   // 兩個(gè)循環(huán)
   // 第一個(gè)循環(huán)根據(jù)序列建立一個(gè)堆
   for(i = n / 2; i >= 0; i--)
  {
       // cout << "break 1" << endl;
       // 從第一個(gè)非葉子節(jié)點(diǎn)開(kāi)始，當(dāng)前非葉子節(jié)點(diǎn)大頂堆，一步步往上推
       headAdjust(a, i, n);
   }
   /*  可以把樹(shù)結(jié)構(gòu)打出來(lái)，驗(yàn)證問(wèn)題，打出來(lái)就是按每層從左到右
   for(int i = 0; i < n; i++)
   {
       cout << a[i] << " ";
   }
   */
   // 第二個(gè)循環(huán)為移除頂點(diǎn)，然后重新建立堆
   for(i = n; i >= 1; i--)
   {
       // cout << "break2" << endl;
       swap(a[0], a[i-1]);
       // 這個(gè)時(shí)候因?yàn)榻粨Q了頂點(diǎn)，因此頂點(diǎn)不滿足大頂堆，但是其余根節(jié)點(diǎn)還是滿足的
       // 因此這里begin參數(shù)傳0就可以
       headAdjust(a, 0, i-1);
       /*
       for(int i = 0; i < n; i++)
       {
           cout << a[i] << " ";
       }
       */
   }
   return;
}

// 6.希爾排序
// 希爾排序是插入排序的升級(jí)，看好的是插入排序相對(duì)基本有序數(shù)組排序較為高效的特點(diǎn)
// 希爾排序的思想是，每次循環(huán)完成對(duì)間隔為increment數(shù)組的排序，直到increment為1，即為完成全數(shù)組排序
void shellSort(int a[], int n)
{
   int increment = n;
   do{
     increment = increment / 3 + 1;
     cout << increment << endl;
     for(int i = increment; i < n; i++)
     {
         // cout << "i:" << i << endl;
         int tmp = a[i];
         if (a[i - increment] > tmp)
         {
             // 尋找當(dāng)前tmp插入的最合適的位置，應(yīng)該插入到比他小的元素的前面，后面的元素都后移
             int j = i - increment;
             for( ; j >= 0 && tmp < a[j]; j-=increment)
             {
                 // cout << "j:" << j << endl;
                 // 后移
                 a[j+increment] = a[j];
             }
             // tmp插入合適位置
             a[j+increment] = tmp;
         }
         // 完成一次按間隔increment抽出來(lái)的數(shù)組的插入排序
     }
   } while(increment > 1);
}

#endif //UNTITLED_SORT_ALGORITHM_H
   int a[10] = {1,4, 2, 7, 2, 3, 8, 9, 4};
   // insertSort(a, 10);
   // bubbleSort(a, 10);
   // quickSort(a, 10);
   // shellSort(a, 10);
   // headSort(a, 10);
   mergeSort(a, 10);
   for(int i = 0; i < 10; i++)
   {
       cout << a[i] << " ";
   }