文章目录

一、前言二、简单插入排序2.1 demo + 运行结果2.2 特点：简单插入排序 三、希尔排序3.1 Demo + 运行结果3.2 特点：希尔排序 四、冒泡排序4.1 Demo + 运行结果4.2 特点：冒泡排序 五、快速排序(面试重点)5.1 Demo + 运行结果5.2 特点：快速排序 六、简单选择排序6.1 Demo + 运行结果6.2 特点：简单选择排序 七、堆排序7.1 Demo + 运行结果7.2 特点：堆排序 八、面试金手指(排序算法的原理 + 排序算法的特点)九、小结

一、前言

数据结构只有五个考点：链表(包括栈和队列)、二叉树、图、查找、排序 排序三考点：所有排序算法比较 + 各个排序算法的原理 + 各个排序算法的特点

二、简单插入排序

2.1 demo + 运行结果

#include <iostream> using namespace std; void InsertSort(int r[],int n) //0号单元为暂存单元和监视哨 { int j=0; for(int i=2; i<=n; i++) { r[0]=r[i]; //用于暂存待排序元素 for ( j=i-1; r[0]<r[j]; j--) //寻找合适的插入位置 r[j+1]=r[j]; //移动 r[j+1]=r[0]; } } int main() { int a[5]; for (int i=0; i<5; i++) cin>>a[i]; cout<<endl; InsertSort(a,5); for (int i=1; i<5; i++) { cout<<a[i]; cout<<" "; } cout<<endl; return 0; }

运行结果：

​​​​

2.2 特点：简单插入排序

简单插入排序： 1、时间复杂度为O(n^2),因为两个循环； 2、空间复杂度为O(1),一个暂存哨兵； 3、只有相邻移动，没有跳动，是一种稳定的排序； 4、适用于序列基本有序的情况。

三、希尔排序

概要：希尔排序，一种高级排序方式，可以认为是简单插入排序的升级版

3.1 Demo + 运行结果

#include <iostream> using namespace std; void shellSort(int r[],int n) { for (int d=n/2; d>=1; d=d/2) { for (int i=d+1; i<=n; i++) //d为增量 { r[0]=r[i]; //0号元素用于暂存 没有意义 int j=0; for ( j=i-d; j>0&&r[0]<r[j]; j=j-d) r[j+d]=r[j]; //记录每次移动d个位置，跳跃移动 r[j+d]=r[0]; } } } int main() { int a[6]; for (int i=0; i<6; i++) cin>>a[i]; cout<<endl; shellSort(a,6); for (int i=1; i<6; i++) { cout<<a[i]; cout<<" "; } cout<<endl; return 0; }

运行结果：

3.2 特点：希尔排序

希尔排序： 1、时间复杂度为O(nlgn)~O(n^2),这是大量重复实验的结果； 2、空间复杂度为O(1),一个暂存哨兵； 3、存在跳动移动，是一种不稳定的排序。

四、冒泡排序

概要：冒泡排序，一种低级排序，便于理解

4.1 Demo + 运行结果

#include <iostream> using namespace std; void bubbleSort(int r[],int n) { int exchange=n; while(exchange!=0) { int bound=exchange; exchange=0; for (int j=1; j<bound; j++) { if(r[j]>r[j+1]) { r[0]=r[j]; //0号元素用于交换暂存 r[j]=r[j+1]; r[j+1]=r[0]; exchange=j; } } } } int main() { int a[6]; for (int i=0; i<6; i++) cin>>a[i]; cout<<endl; bubbleSort(a,6); for (int i=1; i<6; i++) { cout<<a[i]; cout<<" "; } cout<<endl; return 0; }

运行结果：

4.2 特点：冒泡排序

冒泡排序： 1、时间复杂度为O(n^2),因为两个循环； 2、空间复杂度为O(1),一个暂存哨兵； 3、只有相邻移动，没有跳动，是一种稳定的排序。

五、快速排序(面试重点)

概要：快速排序，一种高级排序，可以看作是冒泡排序的升级版

5.1 Demo + 运行结果

#include <iostream> using namespace std; int Partition(int r[],int first,int _end) { int i=first;int j=_end; while(i<j) { while(i<j && r[i]<=r[j]) j--; if(i<j) { int temp=r[i]; r[i]=r[j]; r[j]=temp; i++; } while(i<j && r[i]<=r[j]) i++; if(i<j) { int temp=r[i]; r[i]=r[j]; r[j]=temp; j--; } } return i; } void QuickSort(int r[],int first,int _end) { if(first<_end) { int pivot=Partition(r,first,_end); QuickSort(r,first,pivot-1); QuickSort(r,pivot+1,_end); } } int main() { int a[6]; for (int i=0; i<6; i++) cin>>a[i]; cout<<endl; QuickSort(a,0,5); for (int i=0; i<6; i++) { cout<<a[i]; cout<<" "; } cout<<endl; return 0; }

运行结果：

5.2 特点：快速排序

快速排序： 1、时间复杂度为O(nlgn); 2、空间复杂度为O(1),一个交换变量（交换时合理利用加减可以省略此变量）； 3、存在跳动，是一种不稳定的排序；

六、简单选择排序

概要：简单选择排序，一种低级排序方式，容易理解

6.1 Demo + 运行结果

#include <iostream> using namespace std; void selectSort(int r[],int n) { for (int i=1; i<n; i++) { int index=i; int j=0; for (j=i+1; j<=n; j++) { if(r[j]<r[index]) { r[0]=r[j]; //0号元素用于暂存玩车个交换 // 其实可以不用这样，使用加减法可以不需要暂存元素，这里方便读者理解，用简单的方式 r[j]=r[index]; r[index]=r[0]; } } if(index!=i) { r[0]=r[i]; r[i]=r[index]; r[index]=r[0]; } } } int main() { int a[6]; for (int i=0; i<6; i++) cin>>a[i]; cout<<endl; selectSort(a,6); for (int i=1; i<6; i++) { cout<<a[i]; cout<<" "; } cout<<endl; return 0; }

运行结果：

6.2 特点：简单选择排序

简单选择排序： 1、时间复杂度为O(n^2),因为两个循环； 2、空间复杂度为O(1),一个暂存元素用于实现交换（不是必须，可以用两数加减法实现交换两数）； 3、存在元素跳动，是一种不稳定的排序； 4、没有偏好适用情况，因为最好最坏平均时间复杂度均为O(n^2)

七、堆排序

概要：堆排序，一种高级排序方式，可以看作是简单选择排序的升级版

7.1 Demo + 运行结果

#include <iostream> using namespace std; void shift(int r[],int k,int m) { int i=k,j=2*i; // i 为某个结点 2*i为该结点的左孩子 while(j<=m) // 其左孩子没到结束 说明该结点还是非叶子结点，因为叶子结点是没有左孩子的 { if(j<m && r[j]<r[j+1] ) j++; //j和j+1 比较左右孩子，j指向较大者 if(r[i]>r[j]) break; //当根结点大于左右孩子中较大者，跳出本次循环 else //否则，交换根节点和左右孩子较大者 { r[0]=r[j]; //0号元素用于交换暂存 r[j]=r[i]; r[i]=r[0]; i=j; j=2*i; } } } void heapSort(int r[],int n) { for (int i=n/2; i>=1; i--) shift(r,i,n); for (int i=1; i<n; i++) { r[0]=r[1]; //0号元素用于交换暂存 r[1]=r[n-i+1]; r[n-i+1]=r[0]; shift(r,1,n-i); } } int main() { int a[6]; for (int i=0; i<6; i++) cin>>a[i]; cout<<endl; heapSort(a,6); for (int i=1; i<6; i++) { cout<<a[i]; cout<<" "; } cout<<endl; return 0; }

运行结果：

7.2 特点：堆排序

堆排序： 1、时间复杂度为O(nlgn),因为两个循环； 2、空间复杂度为O(1),一个暂存哨兵； 3、存在跳动，是一种不稳定的排序； 4、适用于选出最小前几个元素和最大的前几个元素

八、面试金手指(排序算法的原理 + 排序算法的特点)

数据结构只有五个考点：链表(包括栈和队列)、二叉树、图、查找、排序 排序三考点：所有排序算法比较 + 各个排序算法的原理 + 各个排序算法的特点

各个排序算法特点先上这六个，排序算法原理以后再上。

简单插入排序： 1、时间复杂度为O(n^2),因为两个循环； 2、空间复杂度为O(1),一个暂存哨兵； 3、只有相邻移动，没有跳动，是一种稳定的排序； 4、适用于序列基本有序的情况。 希尔排序： 1、时间复杂度为O(nlgn)~O(n^2),这是大量重复实验的结果； 2、空间复杂度为O(1),一个暂存哨兵； 3、存在跳动移动，是一种不稳定的排序。

冒泡排序： 1、时间复杂度为O(n^2),因为两个循环； 2、空间复杂度为O(1),一个暂存哨兵； 3、只有相邻移动，没有跳动，是一种稳定的排序。 快速排序： 1、时间复杂度为O(nlgn); 2、空间复杂度为O(1),一个交换变量（交换时合理利用加减可以省略此变量）； 3、存在跳动，是一种不稳定的排序；

简单选择排序： 1、时间复杂度为O(n^2),因为两个循环； 2、空间复杂度为O(1),一个暂存元素用于实现交换（不是必须，可以用两数加减法实现交换两数）； 3、存在元素跳动，是一种不稳定的排序； 4、没有偏好适用情况，因为最好最坏平均时间复杂度均为O(n^2) 堆排序： 1、时间复杂度为O(nlgn),因为两个循环； 2、空间复杂度为O(1),一个暂存哨兵； 3、存在跳动，是一种不稳定的排序； 4、适用于选出最小前几个元素和最大的前几个元素

九、小结

六种排序算法(简单插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序)，完成了。

天天打码，天天进步！！！