本次排序都是按照升序排的

冒泡排序

void bubbleSort(vector<int>& nums)
{int n=nums.size();for(int i=0;i<n-1;i++){bool swapped=false;for(int j=0;j<n-1-i;j++){if(nums[j]>nums[j+1]){swap(nums[j],nums[j+1]);swapped=true;}}if(!swapped)break;}
}
//算法原理: 一共排序n-1次，每一次排序，相鄰元素兩兩比較，一共比較n-1-i次，最后排出一個元素放在數組末尾，n-1次后，排序完成。
//       ? 若還沒有到第n-1次排序，比較元素沒有交換位置，則排序已完成，可提前結束排序。
//時間復雜度: O(N^2)
//空間復雜度: O(1)
//穩定性: 穩定

選擇排序

void SelectSort(vector<int>& nums)
{int n=nums.size();for(int i=0;i<n-1;i++){int minIndex=i;for(int j=i+1;j<n;j++){if(nums[j]<nums[minIndex]){minIndex=j;}}swap(nums[i],nums[minIndex]);}
}
//算法原理: 需要選擇n-1次基準元素，從下標為0開始選取，然后與未排序的元素比較，找到元素最小的下標，交換基準元素和最小元素，一次排序
//       ? 已完成。一共排序n-1次。     ? 
//時間復雜度: O(N^2)
//空間復雜度: O(1)
//穩定性: 不穩定

插入排序

void InsertSort(vector<int>& nums)
{int n=nums.size();for(int i=1;i<n;i++){int key=nums[i],j=i-1;while(j>=0&&nums[j]>key){nums[j+1]=nums[j];j--;}nums[j+1]=key;}
}
//算法原理: 從下標為1開始，令其為key，然后插入到已排序的元素中，找到應該插入的位置。   ? 
//時間復雜度: O(N^2)
//空間復雜度: O(1)
//穩定性: 穩定

希爾排序

void ShellSort(vector<int>& nums)
{int n=nums.size();for(int gap=n/2;gap>0;gap/=2){for(int i=gap;i<n;i++){int key=nums[i],j=i-gap;while(j>=0&&nums[j]>key){nums[j+gap]=nums[j];j-=gap;}nums[j+gap]=key;}}
}
//算法原理: 插入排序的優化，按照gap為間隔，每次排序是預排序，使數組趨于有序化，當gap等于1時，才是真的排序 ? 
//時間復雜度: O(N^2)
//空間復雜度: O(1)
//穩定性: 不穩定

快速排序

快排思想：

int _QuickSort(vector<int> &nums, int left, int right)
{int key = left;left++;while (left <= right){while (left <= right && nums[left] < nums[key])left++;while (left <= right && nums[right] > nums[key])right--;if (left <= right)swap(nums[left++], nums[right--]);}swap(nums[key], nums[right]);return right;
}
void QuickSort(vector<int> &nums, int left, int right)
{if (left > right)return;int key = _QuickSort(nums, left, right);QuickSort(nums, left, key - 1);QuickSort(nums, key + 1, right);
}
//算法原理: 任取待排序元素中的某元素作為基準元素，使左邊元素都小于基準元素，右邊元素都大于基準元素，然后重復該過程，直到所有元素都
//       ? 排序完成。 ? 
//時間復雜度: O(NlogN)
//空間復雜度: O(logN)
//穩定性: 不穩定

歸并排序

void MergeSort(vector<int> &nums, int left, int right)
{if (left >= right) return;int mid = (left + right) >> 1;MergeSort(nums, left, mid);MergeSort(nums, mid + 1, right);vector<int> tmp(right-left+1);int cur1 = left, cur2 = mid + 1, i = 0;while (cur1 <= mid && cur2 <= right)tmp[i++] = nums[cur1] < nums[cur2] ? nums[cur1++] : nums[cur2++];while (cur1 <= mid)tmp[i++] = nums[cur1++];while (cur2 <= right)tmp[i++] = nums[cur2++];for (int i = left; i <= right; i++)nums[i] = tmp[i - left];
}
//算法原理: 將數組分為兩部分，不斷的遞歸，直到數組元素為1或者不能再分，然后合并兩個有序數組。 ? 
//時間復雜度: O(NlogN)
//空間復雜度: O(N)
//穩定性: 穩定

堆排序

void AdjustDown(vector<int>& nums,int n,int parent)
{int child=parent*2+1;while(child<n){if(child+1<n && nums[child+1]>nums[child]) child=child+1;if(nums[child]>nums[parent]){swap(nums[child],nums[parent]);parent=child;child=parent*2+1;}else{break;}}
}
void HeapSort(vector<int>& nums)
{int n=nums.size();//構建大根堆，從最后一個非葉子節點開始for(int i=(n-1-1)/2;i>=0;i--){AdjustDown(nums,n,i);}//排序int end=n-1;while(end>=0){swap(nums[0],nums[end]);AdjustDown(nums,end,0);end--;}
}
//算法原理: 先構建最大堆，然后交換堆頂元素和最后一個元素，這樣最后一個元素就是最大的了，然后再建堆，這樣不斷循環。
//時間復雜度: O(NlogN)
//空間復雜度: O(N)
//穩定性: 穩定

基數排序

void RadixSort(std::vector<int>& nums) {int maxVal=*max_element(nums.begin(),nums.end());int maxDigits=0;while(maxVal){maxVal/=10;maxDigits++;}vector<queue<int>> buckets(10);for(int i=0;i<maxDigits;i++){for(int num : nums){int bucketIndex=num/static_cast<int>(pow(10,i))%10;buckets[bucketIndex].push(num);}int index=0;for(auto& bucket : buckets){while(!bucket.empty()){nums[index++]=bucket.front();bucket.pop();}}}
}
//算法原理:  按照位數排序，按照位數把元素分配到對應的桶中，然后依據先進先出的順序再收集到數組中，這樣依次排個位，十位，百位。
//時間復雜度: O(NlogN)
//空間復雜度: O(N)
//穩定性: 穩定