Sort 方法总结
selectionSort(vector& a)
核心思想：选择最大/小的数移到最前/后
// 1. 计算数组长度// 2. 控制已排序部分的边界
for(i=0; i<n; i++){// 3. 在未排序部分（j到末尾）中寻找真正的maxfor(j=i+1, j<n; j++) find(max);// 3. 将最大的数放至数组头swap(a[i],max);
} 时间复杂度：(n-1) + (n-2) + ...... + 1 = n*(n-1)/2。O(n^2)
不稳定：
原数组[2a, 2b, 1]（2a和2b值相等，2a在2b前），第一轮交换后：[1, 2b, 2a]
bubbleSort(vector& a)
核心思想：比较相邻元素，使较大的元素逐渐 "上浮" 到数组的队尾。
// 1. 计算数组长度// 2. 控制已排序部分边界
for(i=n-1; i>=0; i--){// 3. j在未排序的部分中遍历for(j=0; j<i; j++){// 4. 比较并且交换// 7 6 5 4 3 2 1 ">": 最大的一定会在第一轮冒泡到队尾// "<"：最小的一定会在第一轮冒泡到队尾if(a[j]>a[j+1]) swap(a[j],a[j+1]);}
}
时间复杂度：(n-1) + (n-2) + ...... + 1 = n*(n-1)/2。O(n^2)
稳定：
相邻位置比较交换，且相等时不交换
insertionSort(vector& a)
核心思想：将数组分为 “已排序部分” 和 “未排序部分”，每次从无序列表中取一个元素，插入到有序列表的合适位置。
// 1. 计算数组长度// 2. i控制未排序数组边界
for(i=1; i<n; i++){// 3. j为已排序数组的元素x = a[j]; // x : 待插入元素int j;for(j=i-1; j>=0; j--){// 4. 从后往前依次将有序数组元素与待插入的元素进行比较if(x > a[j]) a[j+1] = a[j]; // 待插入>a[i]，将有序数组的最后一个元素后移一位else break; // 跳出循环}a[j] = x;
}
时间复杂度：(n-1) + (n-2) + ...... + 1 = n*(n-1)/2。O(n^2)
countingSort(vector& a, int m)
核心思想：将元素作为索引
时间复杂度：O(n+k)
空间复杂度：O(k)
为什么用 memset 而不是其他方式？
-
效率更高：
memset是标准库函数，通常由汇编语言实现，对大块内存的初始化速度比手动循环（如for (int i=0; i<=m; i++) count[i]=0）更快。int* count = new int[m + 1];memset(count, 0, sizeof(int) * (m + 1)); -
简洁性：一行代码即可完成整个数组的初始化，无需编写循环逻辑。
mergeSort(vector& a, int l, int r)
核心思想：分治法。将无序数组一分为二，再分为四，直到无法再分割，然后将碎片的元素合并。
// 分治法
void mergeSort(vector<int>& a, int l, int r) {if (l >= r) { //结束条件：无法再分割return;}int m = (l + r) / 2; // 分：边界选择mergeSort(a, l, m);mergeSort(a, m + 1, r);merge(a, l, m, r); // 合：两个有序数组合并
}void merge(vector<int>& a, int l, int m, int r){// 1. 计算分割后两个数组的长度n1 = m-l+1;n2 = r-m;// 2. 设置temp临时数组存放两个分开的有序数组for(i=0; i<n1; i++) temp[i] = a[l+i];for(j=0; j<n2; j++) temp[n1+j] = a[m+1+j]int i = 0, j = n1, k = l;// 3. 当n1=n2while(i<n1 && j<n1+n2){// 比较temp[i] temp[j]，按序放入a[k]a[k++] = temp[i]<=temp[j]?temp[i++]:temp[j++];} // 4. n1 > n2while(i<n1) a[k++] = temp[i++];// 5. n2 > n1while(j<n1+n2) a[k++] = temp[j++];// 6.删除中间数组delete[] temp;
}
QuickSort(vetcot& a, int l, int r)
核心思想：分治法。选择一个基准元素，将数组分为两部分，一部分都比基准元素大，一部分都比基准元素小；然后再对这两部分分别快速排序。
void QuickSort(vector<int>& a, int l, int r)
{if(l >= r) return;// 选择基准元素int povix = Partion(a,l,r);QuickSort(a, l, pivox - 1);QuickSort(a, pivox + 1, r);
}
// a[idx] = 4;
// l r
// 4 5 2 3 6 1 7
// i j
//
// x = 4
int Partition(vector<int>& a, int l, int r){// 1. 随机选择一个基准元素int idx = l + rand() % (r-l+1);// 2. 将当前基准元素和数组首元素交换swap(a[l], a[idx]);// 3. 双指针交换元素int i=l, j=r;int x = a[i];while(i<j){while (i < j && a[j] > x) // 防止右侧的元素都大于x，则 a[j] 访问越界j--;if (i < j) // 如果右侧的元素都大于x，会移到i==j的位置，这时不应该交换swap(a[i], a[j]), ++i;while (i < j && a[i] < x)i++;if (i < j)swap(a[i], a[j]), --j;}return i;
}
