考研数据结构chap8排序

一、概念

1.评价

（1）稳定性

（2）Tn、Sn

2.分类

（1）内部排序

（2）外部排序

二、插入排序

1.直接插入排序(InsertSort)

（1）思路

（2）实现

（3）性能分析

1）Tn

2）Sn

3）稳定性

4）适用性

2.折半插入排序

（1）思路

（2）实现

（3）性能分析

1）Tn

best:O(n^2)

2）Sn

3）稳定性

4）适用性

3.希尔排序(ShellSort)（手算）

（1）背景

（2）思路

（3）实现

（4）性能分析

1）Tn

2）Sn

3）稳定性

4）适用性

三、交换排序

1.冒泡排序（BubbleSort）

（1）思路

（2）实现

（3）性能分析

1）Tn

2）Sn

3）稳定性

4）适用性

2.快速排序（QuickSort）

（1）思路

（2）实现

（3）性能分析

1）Tn

2）Sn

3）稳定性

4）适用性

（4）一次划分 vs 一趟排序

四、选择排序

1.简单选择排序

（1）思想

（2）实现

2.堆排序（以大根堆为eg）

（1）思想

（2）实现

五、归并排序(MergeSort)

1.基本概念

2.思路

3.实现

4.性能分析

（1）Tn

（2）Sn

（3）稳定性

六、基数排序（RadixSort）

1.手算

2.思路

（1）初始化

（2）分配

（3）收集

3.效率分析

（1）Tn

（2）Sn

（3）稳定性

4.application

（1）可以分成的类d较少

（2）每个位置的取值r范围较小

（3）总数n较大

七、外部排序

1.准备

2.思路

3.k路归并

4.Tn

5.优化

（1）多路归并

（2）败者树

1）background

2）说明

3）构建

（3）置换-选择排序（手算）

1）background

2）思想

3）构建

（4）最佳归并树

1）background

2）计算

3）构建（3路平衡归并树）

4）确定虚结点个数

一、概念

1.评价

（1）稳定性

排序前后相同元素的相对位置是否改变

（2）Tn、Sn

2.分类

（1）内部排序

关注算法的Sn、Tn

（2）外部排序

还关注硬盘的读写次数尽量少

二、插入排序

1.直接插入排序(InsertSort)

（1）思路

遍历i个eles，第一个ele当作有序，从第二个ele开始，依次与前面ele比较，if <,交换

（2）实现

//不使用哨兵
void InsertSort(SqList &L,int n){ElemType tmp;//记录待交换结点for (int i = 1; i < n; ++i) {tmp = L->data[i];int j;for ( j = i-1 ; j >=0 && L->data[j] > tmp; j--) {L->data[j+1] = L->data[j];}L->data[j] = tmp;}
}//有哨兵
void InsertSort2(SqList &L,int n){int i,j;for (i = 2; i < n; ++i) {if(L->data[i] < L->data[i-1]){L->data[0] = L->data[i];}for (j = i-1; L->data[0] < L->data[j]; --j) {L->data[j+1] = L->data[j];}L->data[j+1] = L->data[0];}L->len -=1;
}

（3）性能分析

1）Tn

对n个eles，so需要执行n-1次，主要Tn为找位置和交换，so Tn = O(n-1 * n) ~ O(n)

best:全部有序，仅查找即可不用交换 soTn = O(n)

由此可知，在数组有序or大概有序时，直接插入排序效率较高

worst:全部逆序，查找n-1次，每次交换i-1次，so O(n^2)

avg:O(n^2)

2）Sn

O(1)

3）稳定性

当相等时设置不会交换，so稳定

4）适用性

线性表，顺序表和链表均可

2.折半插入排序

（1）思路

利用二分查找查找目标ele应该插入的pos，pos前面的ele前移

（2）实现

//定一个元素位置操作
//挖坑法
int partition(ElemType A[],int low,int high){ElemType pivot=A[low];//存分割值，最左边的元素//∵用pivot存储了定位的值，so可以直接覆盖，不交换了，effective//high 大 high--, 小 A[low] = A[high] low++ high--//间隔着换，low换完high换，high换完low换while(low<high){while(low<high && A[high]>=pivot){//找到比分割值小的元素high--;}A[low]=A[high];while(low<high && A[low] <= pivot){low++;}A[high] = A[low];}//找到位置了A[low] =pivot;return low;
}

void QuickSort(ElemType A[],int low,int high){//low最左边元素，high最右边元素if(low <high) {//至少2个元素//partition->O(n)分成两半while->O(logn)//O(n)O(logn)//最差O(n^2)// reason:有序的数组，递归n次，递归一次O(n)int pivot_pos = partition(A, low, high);//找定哪个位置//pivot:n.支点，中心点//之后再递归前一半QuickSort(A, low, pivot_pos - 1);//后一半QuickSort(A, pivot_pos + 1, high);}
}

（3）性能分析

1）Tn

折半查找仅在查找时做了优化，但是在交换时O(n),总共需要n-1轮，so Tn = O(n^2)

best:O(n^2)

worst:O(n^2)

avg:O(n^2)

2）Sn

O(1)

3）稳定性

查找时可能会发生交换，so不稳定

4）适用性

二分查找适用于顺序表且有序的，so链式表不行

3.希尔排序(ShellSort)（手算）

（1）背景

因为直接插入排序在有序or大致有序时效率较高，so在希尔提出将数组分成若干了子数组，那么在各个子数组中就是大致有序的

（2）思路

依次减少增量d，以距离为d的子ele作为一个子列，在子列中进行插入排序

d一般为数组长度依次/2 ,直到1为止

（3）实现

颜色分组

（4）性能分析

1）Tn

当d直接为1时，直接退化为直接插入排序，O(n^2)

当d在某些范围内，可达到O(n^1.3)

2）Sn

O(1)

3）稳定性

分成不同组的时候可能会交换相对位置，so不稳定,上例可知

4）适用性

因为要求随机存取，so只适用于顺序表

三、交换排序

1.冒泡排序（BubbleSort）

（1）思路

从后->前 or 从前->后，两两交换，大的往后走，一轮可以定一个，so之后就不用比较了，if在一轮中无ele交换，则说明已经有序，排序停止（*考趟数）

（2）实现

void BubbleSort(SSTable A,int n){//排序往往用两层循环，优先写内层，之后写外层//内层循环控制比较交换，外层控制有序数的个数int i,j;bool flag;//添加哨兵，才能实现最高时间复杂度O(n)for (int i=0;i<n-1;i++) {flag = false;//一轮比较下来没有交换的，说明已经有序了//每一轮就定一个，因此j比较次数是动的，用外层控制for (int j = n-1; j > i ; j--) {if(A.elem[j] < A.elem[j-1]){swap(A.elem[j],A.elem[j-1]);flag = true;}}if(false == flag ){//未进行交换return;}}
}

void swap(int &a,int &b){int tmp;tmp = a;a = b;b =tmp;
}

（3）性能分析

1）Tn

best:都是有序的，只用进行n-1轮比较，O(n)

worst:都是逆序，比较n-1轮，每轮交换i-1次，O(n^2)

avg:O(n^2)

2）Sn

O(1)

3）稳定性

当相同时设置不交换，so稳定

4）适用性

顺序表和链表均可

2.快速排序（QuickSort）

（1）思路

以第一个ele作为枢轴，依次与后面eles进行比较，大的放右面，小的放左面，这样每一轮就可以确定一个ele，然后左右分治递归即可

（2）实现

void QuickSort(ElemType A[],int low,int high){//low最左边元素，high最右边元素if(low <high) {//至少2个元素//partition->O(n)分成两半while->O(logn)//O(n)O(logn)//最差O(n^2)// reason:有序的数组，递归n次，递归一次O(n)int pivot_pos = partition(A, low, high);//找定哪个位置//pivot:n.支点，中心点//之后再递归前一半QuickSort(A, low, pivot_pos - 1);//后一半QuickSort(A, pivot_pos + 1, high);}
}

//定一个元素位置操作
//挖坑法
int partition(ElemType A[],int low,int high){ElemType pivot=A[low];//存分割值，最左边的元素//∵用pivot存储了定位的值，so可以直接覆盖，不交换了，effective//high 大 high--, 小 A[low] = A[high] low++ high--//间隔着换，low换完high换，high换完low换while(low<high){while(low<high && A[high]>=pivot){//找到比分割值小的元素high--;}A[low]=A[high];while(low<high && A[low] <= pivot){low++;}A[high] = A[low];}//找到位置了A[low] =pivot;return low;
}

（3）性能分析

1）Tn

主要取决于递归的次数，相当于二叉树

best:每次枢轴可以将左右平分 O(nlogn)

worst:有序or大致有序 O(n^2)

avg: 整体效率接近 O(nlogn)

if每次次枢轴可以将左右平分，那么就可以提高效率

way1：取头部中间尾部，比较大小，取中间

way2：随机取

2）Sn

递归栈的层数（二叉树的高度）O(logn)

3）稳定性

不稳定

4）适用性

顺序表链表均可，但是顺序表效率高

（4）一次划分 vs 一趟排序

408要求一次划分只能定一个ele，一趟排序可以定多个，相当于QuickSort的一层

四、选择排序

每次选择一个定下来最终位置

1.简单选择排序

（1）思想

遍历arr，选择min与第一个交换

（2）实现

void SelectionSort(int A[], int n) {for (int i = 0; i < n - 1; ++i) {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]);}
}

2.堆排序（以大根堆为eg）

（1）思想

初始化堆，建立大根堆

选择根节点，之后重复建堆

（2）实现

void HeapAdjust(int A[],int k,int len){A[0] = A[k];for (int i = 2*k; i <=len ; i*=2) {if(i<len&&A[i]<A[i+1]) i++;if(A[0] >= A[i]) break;else{A[k] = A[i];k=i;}}A[k] = A[0];
}void BuildMaxHeap(int A[],int len){for (int i = len/2; i >0 ; i--) {HeapAdjust(A,i,len);}    
}void HeapSort(int A[],int len){BuildMaxHeap(A,len);for (int i = len; i >1 ; --i) {swap(A[i],A[1]);HeapAdjust(A,i,i-1);}
}

五、归并排序(MergeSort)

1.基本概念

归并：将k个子数列归并成一个子数列，同时变为升序

2.思路

归并排序一般是二路归并，即把两个arr变成一个arr

so先把A[]分成一个个子arr，然后依次进行merge即可

attn：合并时每组需要排序，此处省略

3.实现

int *B = (int *) malloc(7 * sizeof(int));//辅助空间void Merge(int A[], int low, int mid, int high) {int i, j, k;for (k = low; k <= high; ++k) {B[k] = A[k];//先把A中复制到B中}for (i = low, j = mid + 1, k = i; i <= mid && j <= high; ++k) {if (B[i] <= B[j])//排序，升序A[k] = B[i++];elseA[k] = B[j++];}//有一个子arr为nullwhile (i <= mid) A[k++] = B[i++];while (j <= high) A[k++] = B[j++];
}//总过程
void MergeSort(int A[], int low, int high) {if (low < high) {int mid = (low + high) / 2;//先递归只剩1个eleMergeSort(A, low, mid);MergeSort(A, mid + 1, high);//依次mergeMerge(A, low, mid, high);}
}