● 請問Java中collection的sort方法，預設的排序方法是什麼
參考回答：
排序方法是歸并排序
● 手寫代碼：合并兩個排序數組
複制代碼
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | |
● 請問有哪些排序算法
冒泡排序
是最簡單的排序之一了，其大體思想就是通過與相鄰元素的比較和交換來把小的數交換到最前面。這個過程類似于水泡向上升一樣，是以而得名。舉個栗子，對5,3,8,6,4這個無序序列進行冒泡排序。首先從後向前冒泡，4和6比較，把4交換到前面，序列變成5,3,8,4,6。同理4和8交換，變成5,3,4,8,6,3和4無需交換。5和3交換，變成3,5,4,8,6.這樣一次冒泡就完了，把最小的數3排到最前面了。對剩下的序列依次冒泡就會得到一個有序序列。冒泡排序的時間複雜度為O(n^2)。
選擇排序
思想其實和冒泡排序有點類似，都是在一次排序後把最小的元素放到最前面。但是過程不同，冒泡排序是通過相鄰的比較和交換。而選擇排序是通過對整體的選擇。舉個栗子，對5,3,8,6,4這個無序序列進行簡單選擇排序，首先要選擇5以外的最小數來和5交換，也就是選擇3和5交換，一次排序後就變成了3,5,8,6,4.對剩下的序列一次進行選擇和交換，最終就會得到一個有序序列。其實選擇排序可以看成冒泡排序的優化，因為其目的相同，隻是選擇排序隻有在确定了最小數的前提下才進行交換，大大減少了交換的次數。選擇排序的時間複雜度為O(n^2)
插入排序
不是通過交換位置而是通過比較找到合适的位置插入元素來達到排序的目的的。相信大家都有過打撲克牌的經曆，特别是牌數較大的。在分牌時可能要整理自己的牌，牌多的時候怎麼整理呢？就是拿到一張牌，找到一個合适的位置插入。這個原理其實和插入排序是一樣的。舉個栗子，對5,3,8,6,4這個無序序列進行簡單插入排序，首先假設第一個數的位置時正确的，想一下在拿到第一張牌的時候，沒必要整理。然後3要插到5前面，把5後移一位，變成3,5,8,6,4.想一下整理牌的時候應該也是這樣吧。然後8不用動，6插在8前面，8後移一位，4插在5前面，從5開始都向後移一位。注意在插入一個數的時候要保證這個數前面的數已經有序。簡單插入排序的時間複雜度也是O(n^2)。
（我用了連結清單，别人用數組後移更好）
快速排序
在實際應用當中快速排序确實也是表現最好的排序算法。快速排序雖然高端，但其實其思想是來自冒泡排序，冒泡排序是通過相鄰元素的比較和交換把最小的冒泡到最頂端，而快速排序是比較和交換小數和大數，這樣一來不僅把小數冒泡到上面同時也把大數沉到下面。
對5,3,8,6,4這個無序序列進行快速排序，思路是右指針找比基準數小的，左指針找比基準數大的，交換之。
5,3,8,6,4 用5作為比較的基準，最終會把5小的移動到5的左邊，比5大的移動到5的右邊。
5,3,8,6,4 首先設定i,j兩個指針分别指向兩端，j指針先掃描（思考一下為什麼？）4比5小停止。然後i掃描，8比5大停止。交換i,j位置。
5,3,4,6,8 然後j指針再掃描，這時j掃描4時兩指針相遇。停止。然後交換4和基準數。
4,3,5,6,8 一次劃分後達到了左邊比5小，右邊比5大的目的。之後對左右子序列遞歸排序，最終得到有序序列。
上面留下來了一個問題為什麼一定要j指針先動呢？首先這也不是絕對的，這取決于基準數的位置，因為在最後兩個指針相遇的時候，要交換基準數到相遇的位置。一般選取第一個數作為基準數，那麼就是在左邊，是以最後相遇的數要和基準數交換，那麼相遇的數一定要比基準數小。是以j指針先移動才能先找到比基準數小的數。快速排序是不穩定的，其時間平均時間複雜度是O(nlgn)。
堆排序
借助堆來實作的選擇排序，思想同簡單的選擇排序，以下以大頂堆為例。注意：如果想升序排序就使用大頂堆，反之使用小頂堆。原因是堆頂元素需要交換到序列尾部。實作堆排序需要解決兩個問題：
1. 如何由一個無序序列建成一個堆？
2. 如何在輸出堆頂元素之後，調整剩餘元素成為一個新的堆？
堆（二叉堆）可以視為一棵完全的二叉樹，完全二叉樹的一個“優秀”的性質是，除了最底層之外，每一層都是滿的，這使得堆可以利用數組來表示（普通的一般的二叉樹通常用連結清單作為基本容器表示），每一個結點對應數組中的一個元素。
對于給定的某個結點的下标i，可以很容易的計算出這個結點的父結點、孩子結點的下标：
Parent(i) = floor(i/2)，i 的父節點下标
Left(i) = 2i，i 的左子節點下标
Right(i) = 2i + 1，i 的右子節點下标
堆排序（Heap-Sort）是堆排序的接口算法，Heap-Sort先調用Build-Max-Heap将數組改造為最大堆，然後将堆頂和堆底元素交換，之後将底部上升，最後重新調用Max-Heapify保持最大堆性質。
希爾排序
插入排序的一種高效率的實作，也叫縮小增量排序。簡單的插入排序中，如果待排序列是正序時，時間複雜度是O(n)，如果序列是基本有序的，使用直接插入排序效率就非常高。基本思想是：先将整個待排記錄序列分割成為若幹子序列分别進行直接插入排序，待整個序列中的記錄基本有序時再對全體記錄進行一次直接插入排序。
希爾排序的特點是，子序列的構成不是簡單的逐段分割，而是将某個相隔某個增量的記錄組成一個子序列。如上面的例子，第一堂排序時的增量為5，第二趟排序的增量為3。
歸并排序
使用了遞歸分治的思想，先遞歸劃分子問題，然後合并結果。把待排序列看成由兩個有序的子序列，然後合并兩個子序列，然後把子序列看成由兩個有序序列。。。。。倒着來看，其實就是先兩兩合并，然後四四合并。。。最終形成有序序列。空間複雜度為O(n)，時間複雜度為O(nlogn)。
計數排序
如果在面試中有面試官要求你寫一個O(n)時間複雜度的排序算法，你千萬不要立刻說：這不可能！雖然前面基于比較的排序的下限是O(nlogn)。但是确實也有線性時間複雜度的排序，隻不過有前提條件，就是待排序的數要滿足一定的範圍的整數，而且計數排序需要比較多的輔助空間。其基本思想是，用待排序的數作為計數數組的下标，統計每個數字的個數。然後依次輸出即可得到有序序列。
（java中有整型的最大最小值可以直接用）
int MAX = Integer.MAX_VALUE;
int MIN = Integer.MIN_VALUE;
桶排序
假設有一組長度為N的待排關鍵字序列K[1....n]。首先将這個序列劃分成M個的子區間(桶) 。然後基于某種映射函數 ，将待排序列的關鍵字k映射到第i個桶中(即桶數組B的下标 i) ，那麼該關鍵字k就作為B[i]中的元素(每個桶B[i]都是一組大小為N/M的序列)。接着對每個桶B[i]中的所有元素進行比較排序(可以使用快排)。然後依次枚舉輸出B[0]….B[M]中的全部内容即是一個有序序列。
基數排序
一種借助多關鍵字排序思想對單邏輯關鍵字進行排序的方法。所謂的多關鍵字排序就是有多個優先級不同的關鍵字。比如說成績的排序，如果兩個人總分相同，則國文高的排在前面，國文成績也相同則數學高的排在前面。。。如果對數字進行排序，那麼個位、十位、百位就是不同優先級的關鍵字，如果要進行升序排序，那麼個位、十位、百位優先級一次增加。基數排序是通過多次的收配置設定和收集來實作的，關鍵字優先級低的先進行配置設定和收集。
二分法插入排序
二分法插入排序是在插入第i個元素時，對前面的0～i-1元素進行折半，先跟他們中間的那個元素比，如果小，則對前半再進行折半，否則對後半進行折半，直到left<right，然後再把第i個元素前1位與目标位置之間的所有元素後移，再把第i個元素放在目标位置上。
二分插入排序是穩定的與二分查找的複雜度相同；
最好的情況是當插入的位置剛好是二分位置所用時間為O(log₂n);
最壞的情況是當插入的位置不在二分位置所需比較次數為O(n)，無限逼近線性查找的複雜度。
● 手寫代碼：冒泡排序
|
● 手寫代碼：統計排序數組中出現次數最多的元素出現的次數？
public class Main {static void findmost(int[] array){int lastEle=array[0];int maxTime=0;int presentTime=1;int maxEle=array[0];for(int i=1;i<array.length;i++){if(array[i]==lastEle)presentTime++;else{if(presentTime>maxTime){maxTime=presentTime;maxEle=lastEle;}lastEle=array[i];presentTime=1;} if(i==array.length-1 && presentTime>maxTime)// 考慮到比較到最大的元素（排在最後的元素），需要在循環推出前比較一次
{maxTime=presentTime;maxEle=lastEle;}} System.out.println("出現次數最多的元素"+maxEle+" "+"出現的次數"+maxTime);
|
● 請你說一下堆排序的思想？以及怎麼初始建堆？是否穩定？
堆排序是利用堆這種資料結構而設計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間複雜度均為O(nlogn)，它是不穩定的排序。
堆是具有以下性質的完全二叉樹：每個結點的值都大于或等于其左右孩子結點的值，稱為大頂堆；或者每個結點的值都小于或等于其左右孩子結點的值，稱為小頂堆。如下圖：
對堆中的結點按層進行編号，将這種邏輯結構映射到數組中就是下面這個樣子
該數組從邏輯上講就是一個堆結構，用簡單的公式來描述一下堆的定義就是：
大頂堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小頂堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
堆排序的基本思想是：将待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點。将其與末尾元素進行交換，此時末尾就為最大值。然後将剩餘n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。如此反複執行，便能得到一個有序序列了
步驟一構造初始堆。将給定無序序列構造成一個大頂堆（一般升序采用大頂堆，降序采用小頂堆)。
假設給定無序序列結構如下
從最後一個非葉子結點開始（葉結點自然不用調整，第一個非葉子結點arr.length/2-1=5/2-1=1，也就是下面的6結點），從左至右，從下至上進行調整。
找到第二個非葉節點4，由于[4,9,8]中9元素最大，4和9交換。
這時，交換導緻了子根[4,5,6]結構混亂，繼續調整，[4,5,6]中6最大，交換4和6。
此時，我們就将一個無需序列構造成了一個大頂堆。
步驟二将堆頂元素與末尾元素進行交換，使末尾元素最大。然後繼續調整堆，再将堆頂元素與末尾元素交換，得到第二大元素。如此反複進行交換、重建、交換。
a.将堆頂元素9和末尾元素4進行交換
b.重新調整結構，使其繼續滿足堆定義
c.再将堆頂元素8與末尾元素5進行交換，得到第二大元素8.後續過程，繼續進行調整，交換，如此反複進行，最終使得整個序列有序
● 手寫代碼：數組的2-sum,3-sum,問題（leetcode原題）
2SUM問題
最常見的是2SUM問題（1. 2SUM），就是數組中找出兩個數相加和為給定的數。
這道題有兩種思路：
1. 一種思路從首尾搜尋兩個數的和，并逐漸逼近。
2. 另外一種思路是固定一個數A，看SUM-A是否在這個數組之中。
對于第一種思路如下：
此方法是先将數組從小到大排序
設定兩個指針，一個指向數組開頭，一個指向數組結尾，從兩邊往中間走。直到掃到滿足題意的為止或者兩個指針相遇為止。
此時這種搜尋方法就是類似于楊氏矩陣的搜尋方法，就是從楊氏矩陣的左下角開始搜尋，直到找到為止。
如果此時題目條件變為如果沒有找出最接近的2SUM和問題，解決方法跟上面是一樣的
用這種方法2SUM問題的時間複雜度是O(nlogn)O(nlogn)的，主要在于排序的時間。
第二種思路方法如下：
對數組中的每個數建立一個map/hash_map 然後再掃一遍這個數組，判斷target-nums[i]是否存在，如果存在則說明有，不存在繼續找。當然這樣做的話，需要處理一個細節：判重的問題。
代碼如下【注意因為題目中說一定有解是以才下面這樣寫，如果不一定有解，則還要再加一些判斷】
vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,vector<int>> mark;for(int i=0;i<nums.size();i++)mark[nums[i]].push_back(i);for(int i = 0;i<nums.size();i++){if(target-nums[i] == nums[i]){if(mark[nums[i]].size() > 1){vector<int> tmp{i,mark[nums[i]][1]};return tmp;}}else{if(mark.find(target-nums[i]) != mark.end()){vector<int> tmp{i,mark[target-nums[i]][0]};return tmp;}}}} 3-SUM 問題
|
根據給定的容量為 n 的整數數組，找到所有滿足 a + b + c = 0 的三個元素a、b 、c組合，需去重；
解法
修改問題為：滿足 a + b + c = target，target是給定數，原題即 target = 0；
根據題目可知，與 2-SUM 問題類似，在整數數組中不放回的取出三個元素，其和等于給定數（0），不同的是，滿足條件的解有多個而且需要去重；
首先想到的解法是，周遊數組，然後調用 2-SUM 問題中的方法尋找兩個元素相加等于目前元素的補足，最後執行去重操作；這樣的話，查詢的時間複雜度是$O(n^2)$，空間複雜度是$O(n^2)$，去重的時間複雜度是$O(n^2)$，空間複雜度是$O(1)$，這絕對不能算一個好方案；
思考其他思路，既然要去重，可以先對數組執行一次排序，這樣的話在周遊的時候可以跳過相同元素；在确定一個目前元素後，找另外兩個元素相加作為目前元素的補足，此時的解可能是多個的，采用首尾标記的方式可以一次周遊完成查找；
|
● 手寫代碼：5個撲克牌是否是順子，大小王當成任意的
這是劍指offer原題
從撲克牌中随機抽出5張牌，判斷是不是一個順子，即這五張牌是不是連續的。2——10為數字本身，A為1，J為11，Q為12，K為13，而大小王為任意數字。
package org.marsguo.offerproject44;import java.util.Scanner;class SolutionMethod1{public void sortfun(int[] arrays,int start, int end){int numOfZero=0; if(start>=end){ //判斷數組的起始和終止是否相同，相同表示已經都全部排完，傳回
return;
}
int i = start; //i指向數組的起始位
int j = end; //j指向數組的末位
int key = arrays[i]; //選取數組的第一位為關鍵字key，基準元素
boolean flag = true; //設定标志位，用于判斷是i++還是j--;這個很重要
while(i != j){ //如果i≠j，表示還沒有比較完，即即關鍵字左右兩側還不是最小與最大
if(flag){
if(key>arrays[j]){ //從後向前周遊，找到小于key的值，
swap(arrays,i,j); //找到小于key的值後将arrays[i]與此值交換
flag = false;
}else{ //如果沒有找到的話j--，向前周遊
j--;
}else{
if(key<arrays[i]){ //從前向後周遊，找到大于key的值
swap(arrays,i,j); //将此值與arrays[j]進行交換
flag = true;
}else{ //如果沒有找到話就将i++,向後周遊
i++;
//sprint(arrays); //列印每次排序後的數組
sortfun(arrays,start,j-1); //遞歸調用，将基準元素的前半段數組再用此方法進行排序，直到所有都排完為止。
sortfun(arrays,i+1,end); //遞歸調用，将基準元素的後半段數組再用此方法進行排序，直到所有都排完為止。
//System.out.println("排序後的數組是：");
for(int k = 0; k < arrays.length; k++){if(arrays[k] == 0){numOfZero++;}//System.out.print("numOfZero= " + numOfZero + ";"+arrays[k] + ", ");//System.out.print(arrays[k] + ", ");}IsContinuousFun(arrays, numOfZero);}public void swap(int[] array,int i,int j){int temp;temp = array[i];array[i] = array[j];array[j] = temp;}public void IsContinuousFun(int[] array,int numOfZero){ int numOfGap = 0; //判斷數字中間空了多少個0
//System.out.println("numberOfZero = " + numOfZero);
for(int j = 1; j < array.length; j++){
int flag = array[j] - array[j-1]; //用排序數組中後一個數字-前一個數字
if(array[j] == array[j-1] && array[j] != 0){ //如果數組中有重複的非0數字，則不是順子，退出
System.out.println("有重複數字，不是順子牌");
else if(flag != 1 && flag != 0 && array[j-1] != 0){ //判斷不是連續的數字，也不是0，
numOfGap += flag-1; //非0數字間缺少的數字的個數
if(numOfZero != numOfGap){
System.out.println("這不是一個順子撲克牌");
else{
System.out.println("這是一張順子撲克牌");
}
}
}
public class IsContinuous {
public static void main(String[] args){ Scanner scanner = new Scanner(System.in); //掃描鍵盤輸入
System.out.println("請輸入五張牌：");
String str = scanner.nextLine(); //将鍵盤輸入轉化為字元串
String[] temp = str.split(" "); //将字元串用“ ”分開轉化為字元串數組
scanner.close();
int[] array = new int[temp.length]; //定義一個整型數組array
for(int i = 0; i< temp.length; i++){ //将字元串數組強制轉化為整型數組
array[i] = Integer.parseInt(temp[i]); //這種方法非常巧妙
|
● 請你說一說快速排序，并手寫代碼
1、快速排序的基本思想：
快速排序使用分治的思想，通過一趟排序将待排序列分割成兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小。之後分别對這兩部分記錄繼續進行排序，以達到整個序列有序的目的。
2、快速排序的三個步驟：
(1)選擇基準：在待排序列中，按照某種方式挑出一個元素，作為 “基準”（pivot）
(2)分割操作：以該基準在序列中的實際位置，把序列分成兩個子序列。此時，在基準左邊的元素都比該基準小，在基準右邊的元素都比基準大
(3)遞歸地對兩個序列進行快速排序，直到序列為空或者隻有一個元素。
3、選擇基準的方式：
對于分治算法，當每次劃分時，算法若都能分成兩個等長的子序列時，那麼分治算法效率會達到最大。也就是說，基準的選擇是很重要的。選擇基準的方式決定了兩個分割後兩個子序列的長度，進而對整個算法的效率産生決定性影響。最理想的方法是，選擇的基準恰好能把待排序序列分成兩個等長的子序列三種選擇基準的方法：
方法(1)：固定位置
思想：取序列的第一個或最後一個元素作為基準
方法(2)：随機選取基準
引入的原因：在待排序列是部分有序時，固定選取樞軸使快排效率底下，要緩解這種情況，就引入了随機選取樞軸
思想：取待排序列中任意一個元素作為基準
方法(3)：三數取中（median-of-three）
引入的原因：雖然随機選取樞軸時，減少出現不好分割的幾率，但是還是最壞情況下還是O(n^2），要緩解這種情況，就引入了三數取中選取樞軸
分析：最佳的劃分是将待排序的序列分成等長的子序列，最佳的狀态我們可以使用序列的中間的值，也就是第N/2個數。可是，這很難算出來，并且會明顯減慢快速排序的速度。這樣的中值的估計可以通過随機選取三個元素并用它們的中值作為樞紐元而得到。事實上，随機性并沒有多大的幫助，是以一般的做法是使用左端、右端和中心位置上的三個元素的中值作為樞紐元。顯然使用三數中值分割法消除了預排序輸入的不好情形，并且減少快排大約14%的比較次數。
固定位置示例程式：
public class QuickSort {
public static void main(String[] args) {
int[] a = {1, 2, 4, 5, 7, 4, 5 ,3 ,9 ,0};
System.out.println(Arrays.toString(a));
quickSort(a);
System.out.println(Arrays.toString(a));
}
public static void quickSort(int[] a) {
if(a.length>0) {
quickSort(a, 0 , a.length-1);
}
}
private static void quickSort(int[] a, int low, int high) { //1,找到遞歸算法的出口
if( low > high) {
return;
} //2, 存
int i = low;
int j = high;
//3,key
int key = a[ low ]; //4，完成一趟排序
while( i< j) {
//4.1 ，從右往左找到第一個小于key的數
while(i<j && a[j] > key){
j--;
} // 4.2 從左往右找到第一個大于key的數
while( i<j && a[i] <= key) {
i++;
} //4.3 交換
if(i<j) {
int p = a[i];
a[i] = a[j];
a[j] = p;
}
} // 4.4，調整key的位置
int p = a[i];
a[i] = a[low];
a[low] = p;
//5, 對key左邊的數快排
quickSort(a, low, i-1 );
//6, 對key右邊的數快排
quickSort(a, i+1, high);
四種優化方式：
優化1：當待排序序列的長度分割到一定大小後，使用插入排序
原因：對于很小和部分有序的數組，快排不如插排好。當待排序序列的長度分割到一定大小後，繼續分割的效率比插入排序要差，此時可以使用插排而不是快排
優化2：在一次分割結束後，可以把與Key相等的元素聚在一起，繼續下次分割時，不用再對與key相等元素分割
優化3：優化遞歸操作
快排函數在函數尾部有兩次遞歸操作，我們可以對其使用尾遞歸優化
優點：如果待排序的序列劃分極端不平衡，遞歸的深度将趨近于n，而棧的大小是很有限的，每次遞歸調用都會耗費一定的棧空間，函數的參數越多，每次遞歸耗費的空間也越多。優化後，可以縮減堆棧深度，由原來的O(n)縮減為O(logn)，将會提高性能。
優化4：使用并行或多線程處理子序列
● 你最熟悉什麼算法？給我說一下原理或者排序過程？它的優缺點是什麼？你知道什麼排序算法，介紹他們的實作方法，時間複雜度和空間複雜度，是否穩定，快排基準點怎麼選擇，
最熟悉排序算法，常見的排序算法有以下幾種
1、插入排序，即逐個處理待排序的記錄，每個記錄與前面已排序的子序列進行比較，将它插入子序列中正确位置，時間複雜度O（n^2）,空間複雜度為O(1)，是穩定排序，插入排序不适合對于資料量比較大的排序應用，但是如果量級小餘千，那麼插入排序還是一個不錯的選擇，
2、冒泡排序，它重複地走訪過要排序的元素，依次比較相鄰兩個元素，如果他們的順序錯誤就把他們調換過來，直到沒有元素再需要交換，排序完成。這個算法的名字由來是因為越小(或越大)的元素會經由交換慢慢“浮”到數列的頂端。他的時間複雜度和空間複雜度分别是O（n^2）,空間複雜度是O（1）屬于穩定排序，冒泡排序對于少數元素之外的數列排序是很沒效率的。
3、選擇排序，初始時在序列中找到最值元素，放到序列的其實位置作為已排序序列，再在剩餘未排序元素中繼續尋找最小（大）元素，放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。他的時間複雜度是O（n^2）,空間複雜度是O（1）屬于不穩定排序
4、shell排序，是插入排序的更新版，屬于不穩定排序，希爾排序通過将比較的全部元素分為幾個區域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然後算法再取越來越小的步長進行排序，算法的最後一步就是普通的插入排序，但是到了這步，需排序的資料幾乎是已排好的了（此時插入排序較快）。
假設有一個很小的資料在一個已按升序排好序的數組的末端。如果用複雜度為O(n^2)的排序（冒泡排序或直接插入排序），可能會進行n次的比較和交換才能将該資料移至正确位置。而希爾排序會用較大的步長移動資料，是以小資料隻需進行少數比較和交換即可到正确位置。希爾排序的時間複雜度根據步長序列的不同而不同，空間複雜度O（1）
5、歸并排序，歸并排序的實作分為遞歸實作與非遞歸(疊代)實作。屬于穩定排序，遞歸實作的歸并排序是算法設計中分治政策的典型應用，我們将一個大問題分割成小問題分别解決，然後用所有小問題的答案來解決整個大問題。非遞歸(疊代)實作的歸并排序首先進行是兩兩歸并，然後四四歸并，然後是八八歸并，一直下去直到歸并了整個數組。他的時間複雜度是O（nlogn）空間複雜度是O（n）
6、堆排序，其實作原理為首先将數組構造成一個最大/最小堆，将堆頂元素和堆尾元素互換，調出堆頂元素，重新構造堆，重複步驟直至堆中元素都被調出。堆排序的時間複雜度為O（nlogn）空間複雜度為O（1），屬于不穩定排序。
7、快速排序，快排使用分治政策，首先從序列中挑出一個元素作為基準，然後把比基準小的元素放在一邊，把比基準大的元素放在另一邊，重複這個步驟，直至子序列的大小是0/1.快排的時間複雜度是O（nlogn）空間複雜度是O（logn）屬于不穩定算法，對于快排的基準元素選取，可以采用三者取中法，三個随機值的中間一個。為了減少随機數生成器産生的延遲，可以選取首中尾三個元素作為随機值
排序算法的适用情況：
當n比較小且基本有序，可采用直接插入或冒泡，否則采用直接插入
當n較大，可以采用快排，歸并，堆排序，快排是目前基于比較的内部排序中最好的方法，堆排序所需的輔助空間少于快速排序，并且不會出現快速排序可能出現的最壞情況。這兩種排序都是不穩定的。
若要求排序穩定，則可選用歸并排序。但前面介紹的從單個記錄起進行兩兩歸并的排序算法并不值得提倡，通常可以将它和直接插入排序結合在一起使用。先利用直接插入排序求得較長的有序子序列，然後再兩兩歸并之。因為直接插入排序是穩定的，是以改進後的歸并排序仍是穩定的。
● 請你說一下快排如何實作？
首先選擇一個軸值，小于軸值的元素被放在數組中軸值左側，大于軸值的元素被放在數組中軸值右側，這稱為數組的一個分割(partition)。快速排序再對軸值左右子數組分别進行類似的操作
選擇軸值有多種方法。最簡單的方法是使用首或尾元素。但是，如果輸入的數組是正序或者逆序時，會将所有元素分到軸值的一邊。較好的方法是随機選取軸值
代碼：
template <class Elem>
int partition(Elem A[],int i,int j)
{ //這裡選擇尾元素作為軸值,軸值的選擇可以設計為一個函數
//如果選擇的軸值不是尾元素，還需将軸值與尾元素交換
int pivot = A[j];
int l = i - 1;
for(int r = i;r < j;r++)
if(A[r] <= pivot)
swap(A,++l,r); swap(A,++l,j);//将軸值從末尾與++l位置的元素交換
|