考研排序复习笔记
-
插入排序
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 9
//折半插入排序
void ZBInsertSort(int A[],int n){
int i,j,high,low,mid;
for(i=2;i<=n;i++){
A[0] = A[i];
low = 1;high = i-1;
while(low<=high){
mid=(low+high)/2;
if(A[mid]>A[0]){
high=mid-1;
}
else{
low = mid+1;
}
}
for(j = i-1;j>=high+1;--j){
A[j+1] = A[j];
}
A[high+1] = A[0];
}
}
//直接插入排序（带哨兵）
void InsertSort(int A[],int n){
int i,j;
for(i=2;i<=n;i++){
if(A[i]<A[i-1]){
A[0] = A[i];
for(j =i-1;A[0]<A[j];j--){
A[j+1] = A[j];
}
A[j+1] = A[0];
}
}
}
//插入排序的复杂度都是O(n^2)
int main(){
int A[] = {0,49,38,65,97,76,13,27,49};
for(int i = 1;i<MaxSize;i++){
printf("%d ",A[i]);
}
ZBInsertSort(A,8);
printf("\n");
for(int i = 1;i<MaxSize;i++){
printf("%d ",A[i]);
}
return 0;
}
空间复杂度：$O(1)$
平均时间复杂度$：O(n^2)$
相当于从A[2]一路顺序查找下去，是A[1]往后逐渐有序。
开始后A[1]----A[2]----是有序的
这部分可以使用折半查找
复习折半查找的停止条件：low>high
-
A[0]>mid
- 数在mid后面，low = mid + 1
-
A[0]<mid
- 说明数在mid前面部分，high = mid - 1
-
希尔排序（Shell Sort）
灵感来源：插入排序在基本有序的情况下表现很好
所以希尔排序的思想是基于这种基本有序
希尔排序代码实现
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 9
//希尔排序
//往后逐个对比
void ShellSort(int A[],int n){
int d,i,j;
for(d = n/2;d>=1;d = d/2){
for(i=d+1;i<=n;++i){
if(A[i]<A[i-d]){
A[0] = A[i];
for(j=i-d;j>0 && A[0]<A[j];j-=d)
A[j+d] = A[j];
A[j+d] = A[0];
}
}
}
}
//希尔排序
//一串捋直了再下一串
void testShellSort(int A[],int n){
int d,i,j;
for(d = n/2;d>=1;d=d/2){ //步长变化
for(i=1;i<=d;i++){ //多少组
for(i=d+1;i<=n;i+=d){ //遍历每一组的所有数字
if(A[i] < A[i-d]){
A[0] = A[i]; //小的放在A[0]
for(j=i-d;j>0 && A[0]<A[j];j-=d){
A[j+d] = A[j];
}
A[j+d] = A[0];
}
}
}
}
}
//插入排序的复杂度都是O(n^2)
int main(){
int A[] = {NULL,49,38,65,97,76,13,27,49};
for(int i = 1;i<MaxSize;i++){
printf("%d ",A[i]);
}
testShellSort(A,8);
printf("\n");
for(int i = 1;i<MaxSize;i++){
printf("%d ",A[i]);
}
return 0;
}
以上第一种是：i++，逐个逐个比较各自的串
第二种是 只扫描A[0] -> A[1] ->A[2]->>>一个d，在每次扫描到一个串的时候完成这个串的排序
$空间复杂度为O(1)$
$时间复杂度与选取的d挂钩$
当第一次选取d=1时，希尔排序 退化为 插入排序
稳定性分析：
稳定性：不稳定
且只使用于顺序表，不使用于链表
-
冒泡排序（Bubble Sort）
基于交换的排序：根据序列中两个元素的关键字的比较结果来对换两个记录在序列中的位置
当最后一趟没有任何交换时，说明已经有序了
#include<stdio.h>
#include<stdlib.h>
void swap(int &a,int &b){
int temp;
temp = a;
a = b;
b = temp;
}
//MM手写版 version.1
void BubbleSort(int A[],int n){
for(int i=1;i<=n-1;i++){
bool flag = false;
for(int j=n-1;j>=i;j--){ //犯错1：int j=n-1;j=i;j-- 每次判断的时候都会重新定义j导致永远退不出循环！
if(A[j]<A[j-1]){
swap(A[j],A[j-1]);
flag = true;
}
}
if(flag == false){ //犯错2：if flag == false 太粗心！
break;
}
}
}
// mm手写版与王道给的基本一致
//王道版
void WD_BubbleSort(int A[],int n){
for(int i=0;i<n-1;i++){ //交换的趟数 = n-1
bool flag = false; //表示本趟冒泡是否发生交换的标志
for(int j=n-1;j>i;j--){ //一趟冒泡
if(A[j-1] > A[j]){ //若为逆，则交换
swap(A[j-1],A[j]);
flag = true;
}
}
if(flag == false){ //本趟遍历之后如果没有发生交换，则已经有序
break;
}
}
}
int main(){
int list[] = {49,38,65,97,76,13,27,49};
for(int i = 0;i<=7;i++){
printf("%d ",list[i]);
}
printf("\n");
BubbleSort(list,8);
for(int i = 0;i<=7;i++){
printf("%d ",list[i]);
}
printf("\n");
return 0;
}
冒泡排序显然是稳定的
且适用于链表
代码给的是从后往前冒，其实从前往后也是可以的所以要注意题目给的条件
易忘点：如果一趟排序过程未发生“交换”，则可以提前结束
-
快速排序
如名字所言：确实是最厉害的
核心思想：
$high所指的>基准:high--$
$high所指 < 基准:放到low那里$
$low所指 < 基准:low++$
$low所指 > 基准:放到high那里$
终止条件: $low == high$
于是划分为$$【<A】 | 【A】 | 【>A】$$
再分别在两边重复以上过程
#include<stdio.h>
#include<stdlib.h>
//Partition （分割）
int Partition(int A[],int low,int high){
int pivot = A[low]; //pivot:枢轴
while(low < high){
while(low<high && A[high] >=pivot) --high; //high前推找比pivot小的
A[low] = A[high];
while(low<high && A[low] <=pivot) ++low; //low后推找比pivot大的
A[high] = A[low];
}
A[low] = pivot;
return low;
}
void QuickSort(int A[],int low,int high){
if(low<high){ //递归跳出的条件
int pivotpos = Partition(A,low,high); //划分
QuickSort(A,low,pivotpos-1); //划分左子表
QuickSort(A,pivotpos+1,high); //划分右子表
}
}
int main(){
int list[] = {49,38,65,97,76,13,27,49};
for(int i = 0;i<=7;i++){
printf("%d ",list[i]);
}
printf("\n");
QuickSort(list,0,7);
for(int i = 0;i<=7;i++){
printf("%d ",list[i]);
}
printf("\n");
return 0;
}
空间复杂度：
其实分析起来
本质上就像一个二叉树
最好/最坏情况分析：
快速排序的稳定性：不稳定！
-
简单选择排序
从头到尾扫描 1 次
然后交换位置
从头到尾扫描 2 次
然后交换位置
从头到尾扫描 3 次
然后交换位置
$n个元素的简单排序需要处理n-1趟$
代码实现：
#include<stdio.h>
#include<stdlib.h>
void swap(int &a,int &b){
int temp;
temp = a;
a = b;
b = temp;
}
//MM手写版 version.1
//王道版交换的是index，我交换的是数据
void SelectSort(int A[],int n){
for(int i=0;i<n;i++){ //需要排n-1次 *error：i<n-1就行了 因为n=8,最后一个元素实际下标是7
int min = A[i];
for(int j=i;j<n;j++){ //逐行扫描
if(A[j]<min){
swap(min,A[j]);
}
}
A[i] = min;
}
}
//王道版 简单选择排序
void WD_SelectSort(int A[],int n){
for(int i=0;i<n-1;i++){ //一共排n-1趟
int min = i; //记录最小元素位置
for(int j=i+1;j<n;j++)
if(A[j]<A[min]) min=j; //更新最小元素位置
if(min != i) swap(A[i],A[min]);
}
}
int main(){
int list[] = {49,38,65,97,76,13,27,49};
for(int i = 0;i<=7;i++){
printf("%d ",list[i]);
}
printf("\n");
WD_SelectSort(list,8);
for(int i = 0;i<=7;i++){
printf("%d ",list[i]);
}
printf("\n");
return 0;
}
可以使用链表来练练手！
标签：include,笔记,int,mid,c++,high,low,排序,考研 From： https://www.cnblogs.com/jinwan/p/17575364.html