一-排序的基本概念
二-插入排序
1-直接插入排序
2-折半插入排序
3-希尔排序
三-交换排序
1-冒泡排序
2-快速排序
①确定分界点（任意值）（分治）
常用有三种：取左边界、取右边界、取中间值
②小于分界点的，放在分界点左边，大于分界点的，放在分界点右边（实现重点）（双指针）
③递归处理左右两边，即将左边排好序、将右边排好序
// 定义快速排序函数，q[] 是待排序数组，l 是左边界，r 是右边界
void quick_sort(int q[], int l, int r){// 如果区间长度小于等于 1，直接返回if(l >= r) return;// 初始化双指针：i 从左边界前一个位置开始，j 从右边界后一个位置开始int i = l - 1, j = r + 1;// 取中间位置的元素作为基准值（注意加括号确保优先级正确）int x = q[(l + r) >> 1];// 当 i 和 j 没有相遇时，继续划分while(i < j){// i 向右移动，直到找到一个不小于 x 的元素跳出循环do i++; while(q[i] < x);// j 向左移动，直到找到一个不大于 x 的元素跳出循环do j--; while(q[j] > x);// 如果 i 仍然在 j 左边，交换 q[i] 和 q[j]if(i < j) swap(q[i], q[j]);}//遍历完成后j指向x// 递归处理左半部分（包含等于 x 的元素）quick_sort(q, l, j);// 递归处理右半部分quick_sort(q, j + 1, r);
}四-选择排序
1-简单选择排序
2-堆排序
五-归并排序
①确定分界点：mid=(l+r)/2
②递归排序左边和右边
③将两个有序序列合并为一个有序序列(实现重点)
//对数组q的区间[l,r]进行排序
void merge_sort(int q[], int l, int r){//如果区间长度为1或0，直接返回（此时已经排好）if(l>=r) return;//取mid为边界值int mid=(l+r)>>1;//递归排序左半部分merge_sort(q,l,mid);//递归排序右半部分merge_sort(q,mid+1,r);//k是辅助数组的下标，i是左边数组起始，j是右边数组起始int k=0, i=l, j=mid+1;while(i<=mid&&j<=r)//谁小谁先放if(q[i]<=q[j]) tmp[k++]=q[i++];else tmp[k++]=q[j++];//将剩余元素拷贝到tmpwhile(i<=mid) tmp[k++]=q[i++];while(j<=r) tmp[k++]=q[j++];//将tmp中排好序的元素复制回原数组q的对应位置for(i=l, j=0; i<=r; i++, j++) q[i]=tmp[j];
}
