排序
文章目录
- 排序
- 插入排序
- 直接插入排序
- 折半查找插入排序
- 希尔排序
- 选择排序
- 简单选择排序
- 堆排序
- 一、构建堆
- **堆有以下性质**:
- **堆的存储方式**:
- **设计堆**
- 数据结构
- 堆的维护
- 堆的初始化
- 创建堆
- 插入一个元素
- 删除一个元素
- 返回有效元素的个数
- 获得优先级最高的元素
- 全部代码
- 二、使用堆进行排序
- 交换排序
- 冒泡排序
- 快速排序
下面针对排序都是升序,且排序的元素都是整型。
插入排序
直接插入排序
原理:将无序的元素插入到有序的序列
基本思路:
- 将第一个元素作为一个有序序列,从第二个开始依次添加元素到有序序列中
- 现假设要添加第i个元素到有序序列中去,有序序列最后一个元素下标为i-1,我们只需要确定第i个元素在有序序列中的位置即可
- 在确定位置时,应满足如果要插入的元素小于前一个元素,那么前一个元素往后移,直到遇到插入元素大于等于前一个元素为止
- 要插入元素有n-1个,因此外循环为n-1;内循环是为当前元素找插入位置,判断条件为前面元素大于插入元素
void InsertSort(int* arr,int n){//i为第几个元素插入到有序序列中,j为遍历有序序列的下标//temp保存当前插入元素的值,因为前面元素要向后移动,覆盖插入元素的值,所以要保存int i,j,temp;for(i=1;i<n;i++){//从有序序列最后一个开始j=i-1;temp=arr[i];while(j>=0 && arr[j]>temp){//后移arr[j+1]=arr[j];j--;}//arr[j]<=temparr[j+1]=temp;}
}
折半查找插入排序
原理:和直接插入排序相似,只是在找插入位置时,使用折半查找,减少了比较次数,但是元素移动次数没有改变
基本思路:
- 在有序序列中找插入元素的位置
// 1 2 4 5 7 9 e==6
//mid=2,4<6,low=mid+1=3
//mid=4,7>e,high=mid-1=3初始化低位和高位:low = 0,high = len - 1,表示查找的初始范围是数组的从头到尾。
避免加法溢出:mid = low + (high - low) / 2;,避免 low + high 可能导致的溢出问题。
查找过程:
如果 arr[mid] < e,则说明目标元素 e 应该插入到 mid 的右边,即更新 low = mid + 1。
如果 arr[mid] > e,则目标元素 e 应该插入到 mid 的左边,即更新 high = mid - 1。
如果 arr[mid] == e,说明目标元素已经存在,可以直接返回当前位置+1。
返回插入位置:
当 low 大于 high 时,目标元素没有找到,low 位置就是元素 e 应该插入的位置。
int BinarySearchInsertPosition(int* arr, int len, int e) {int low = 0, high = len - 1;// 避免加法溢出,防止 high + low 可能导致溢出int mid = low + (high - low) / 2;// 查找插入位置while (low <= high) {if (arr[mid] < e) {// 如果中间元素小于目标元素,则查找右半部分low = mid + 1;} else if (arr[mid] > e) {// 如果中间元素大于目标元素,则查找左半部分high = mid - 1;} else {// 如果中间元素等于目标元素,返回当前的 mid,表示可以插入到该位置return mid + 1;}// 重新计算中间索引mid = low + (high - low) / 2;}// 如果没有找到相等的元素,low 就是应该插入的位置return low;
}void Bsearch_InsertSort(int* arr,int n){int i,j,temp;for(i=1;i<n;i++){j=i-1;temp=arr[i];//查找应插入位置int pos=BinarySearchInsertPosition(arr,n,temp);//移动元素for(int k=i;k>pos;k--){arr[k]=arr[k-1];}arr[pos]=temp;}
}
希尔排序
原理:希尔排序又叫缩小增量排序法,设置一个增量dx
,将待排序序列进行分组,如果dx=5
的话,那么待排序序列足够长的话,会被分为5组,即[(0,5,10,15…),(1,6,11,16…)…(4,9,14,19)](这里的数字都是下标),在这5组在组内分别排序后,每次从这5个分组按序取一个元素,直到所有元素取完;之后dx=2
,再次分组排序,最后dx=1
,就是直接插入排序。
基本步骤:
-
初始化步长,通常设置为数组长度的一半
-
对每个分组进行插入排序
void ShellSort(int* arr,int n){int i,j,temp;for(int gap=n/2;gap>0;gap/=2){for(i=gap;i<n;i++){temp=arr[i];j=i;while(j>=gap&&arr[j-gap]>temp){arr[j]=arr[j-gap];j-=gap;}arr[j]=temp;}} } 解释:假设数组的长度为16,第一次时,gap=8,i从8到15,分为了8组,依次和前面的i-gap进行比较排序第二次时,gap=4,i从4到15,每次从第二个元素开始排序。要保证下一个元素排序时,前面的元素是有序的,如果从12到15排序,前面3个元素不一定是有序的因此必须从gap开始,第一个元素有序,这样是正确的。然后依次轮到第一组的第二个元素,第二组的第二个元素,第三组的第二个元素,第四组的第二个元素。
选择排序
简单选择排序
void SelectionSort(int* arr,int n){int i,j,temp;//每次选择一个小的元素到序列最前面,只需选择n-1个元素就可以让序列有序for(i=0;i<n-1;i++){//j从i开始for(j=i;j<n;j++){if(arr[i]>arr[j]){temp=arr[i];arr[i]=arr[j];arr[j]=temp;}}}
}
堆排序
一、构建堆
堆排序要利用一个数据结构——堆,根据堆顶元素的不同意义,分为大顶堆和小顶堆。所以下面先介绍堆的性质和如何创建堆等。
堆有以下性质:
-
堆中某个节点的值不大于或不小于其父节点的值
-
堆总是一棵完全二叉树(因此可以使用数组来存储)
堆的存储方式:
从堆的概念可知,堆是一棵完全二叉树,因此可以层序的规则采用顺序的方式来高效存储。
-
假设i为节点在数组中的下标,则有:
-
如果i为0,则i表示的节点为根节点,否则i节点的双亲节点为 (i - 1)/2。
-
如果2 * i + 1 小于节点个数,则节点i的左孩子下标为2 * i + 1,否则没有左孩子。
-
如果2 * i + 2 小于节点个数,则节点i的右孩子下标为2 * i + 2,否则没有右孩子。
设计堆
下面我们都以大顶堆为例。
数据结构
#define MAXSIZE_HEAP 100
typedef struct Heap{int *arr;int Size;//堆的大小int usedSize;//现有多少个元素
}MyHeap;
堆的维护
-
向上调整
向上调整主要用于新元素添加到堆中去时,用于和父节点进行比较交换,以维护堆的性质。
基本步骤:
- 不断和父节点作比较,判断是否交换,一直到根节点
void shiftUp(MyHeap* heap,int child){//获得父节点的下标int parent=(child-1)/2;while(child>0){if(heap->arr[parent]>=heap->arr[child]){//满足大顶堆的性质,结束调整break;}else{//做交换int temp=heap->arr[parent];heap->arr[parent]=heap->arr[child];heap->arr[child]=temp;//交换之后影响上面的树,继续调整child=parent;parent=(child-1)/2;}} }
-
向下调整
向下调整主要用于堆的创建和堆顶元素发生改变时。
void shiftDown(MyHeap* heap,int parent){//有孩子的话,左孩子一定有int child=2*parent+1;while(child<heap->usedSize){if(child+1<heap->usedSize&&heap->arr[child+1]>heap->arr[child]){//如果右孩子存在且大于左孩子的值,获得要和孩子节点交换的下标child=child+1;}if(heap->arr[parent]>=heap->arr[child]){//如果父节点大于等于孩子节点,满足大顶堆性质break;}else{//交换int temp=heap->arr[parent];heap->arr[parent]=heap->arr[child];heap->arr[child]=temp;//交换之后可能会影响下面的子树,如果交换的这个孩子节点有孩子的话,调整这棵子树。parent=child;child=2*parent+1;}} }
堆的初始化
//Size为指定的初始化堆的大小
void InitHeap(MyHeap* heap, int* arr, int len, int Size) {heap->arr = (int*)malloc(sizeof(int) * Size);heap->Size = Size;heap->usedSize = 0;for (int i = 0; i < len; i++) {heap->arr[i] = arr[i];heap->usedSize++;}
}
创建堆
基本步骤:
- 找到最后一个非叶子节点
- 不断向下调整,直到到达根节点,全部调整完成,堆也就创建好了
void CreateHeap(MyHeap* heap){//找到最后一个叶子节点的父节点,从这里开始向下调整,这时,整棵树还是比较乱的int StartRoot=(heap->usedSize-1-1)/2;for(;StartRoot>=0;StartRoot--){shiftDown(heap,StartRoot);}
}
插入一个元素
插入元素都从最后一个位置插入
void offer(MyHeap* heap,int e){//先判断堆是否还可以添加元素if(heap->usedSize==heap->Size){//堆满了,扩容int* temp=(int*)malloc(sizeof(int)*2*heap->Size);for(int i=0;i<heap->Size;i++){temp[i]=heap->arr[i];}free(heap->arr);heap->arr=temp;heap->Size=2*heap->Size;}heap->arr[(heap->usedSize)++]=e;//插入元素后,进行向上调整shiftUp(heap,heap->usedSize-1);
}
删除一个元素
删除元素一定是堆顶元素,因为我们总是获得优先级最高的元素。
int poll(MyHeap* heap){if(heap->usedSize>0){int ret=heap->arr[0];heap->arr[0]=heap->arr[heap->usedSize-1];//向下调整shiftDown(heap,0);(heap->usedSize)--;return ret;}else{printf("Heap is empty.");exit(1);}}
返回有效元素的个数
int size(MyHeap* heap){return heap->usedSize;
}
获得优先级最高的元素
int peek(MyHeap* heap){if(heap->usedSize>0){return heap->arr[0];}else{printf("Heap is empty.");exit(1);}
}
全部代码
#define MAXSIZE_HEAP 100
typedef struct Heap{int *arr;int Size;//堆的大小int usedSize;//现有多少个元素
}MyHeap;void shiftUp(MyHeap* heap,int child);
void shiftDown(MyHeap* heap,int parent);
void InitHeap(MyHeap* heap,int* arr,int len,int Size);
void CreateHeap(MyHeap* heap);
void offer(MyHeap* heap,int e);
int poll(MyHeap* heap);
int size(MyHeap* heap);
int peek(MyHeap* heap);//--------------------------------------------------------------
void shiftUp(MyHeap* heap,int child){//获得父节点的下标int parent=(child-1)/2;while(child>0){if(heap->arr[parent]>=heap->arr[child]){//满足大顶堆的性质,结束调整break;}else{//做交换int temp=heap->arr[parent];heap->arr[parent]=heap->arr[child];heap->arr[child]=temp;//交换之后影响上面的树,继续调整child=parent;parent=(child-1)/2;}}
}void shiftDown(MyHeap* heap,int parent){//有孩子的话,左孩子一定有int child=2*parent+1;while(child<heap->usedSize){if(child+1<heap->usedSize&&heap->arr[child+1]>heap->arr[child]){//如果右孩子存在且大于左孩子的值,获得要和孩子节点交换的下标child=child+1;}if(heap->arr[parent]>=heap->arr[child]){//如果父节点大于等于孩子节点,满足大顶堆性质break;}else{//交换int temp=heap->arr[parent];heap->arr[parent]=heap->arr[child];heap->arr[child]=temp;//交换之后可能会影响下面的子树,如果交换的这个孩子节点有孩子的话,调整这棵子树。parent=child;child=2*parent+1;}}
}//Size为指定的初始化堆的大小
void InitHeap(MyHeap* heap, int* arr, int len, int Size) {heap->arr = (int*)malloc(sizeof(int) * Size);heap->Size = Size;heap->usedSize = 0;for (int i = 0; i < len; i++) {heap->arr[i] = arr[i];heap->usedSize++;}
}void CreateHeap(MyHeap* heap){//找到最后一个叶子节点的父节点,从这里开始向下调整,这时,整棵树还是比较乱的int StartRoot=(heap->usedSize-1-1)/2;for(;StartRoot>=0;StartRoot--){shiftDown(heap,StartRoot);}
}void offer(MyHeap* heap,int e){//先判断堆是否还可以添加元素if(heap->usedSize==heap->Size){//堆满了,扩容int* temp=(int*)malloc(sizeof(int)*2*heap->Size);for(int i=0;i<heap->Size;i++){temp[i]=heap->arr[i];}free(heap->arr);heap->arr=temp;heap->Size=2*heap->Size;}heap->arr[(heap->usedSize)++]=e;//插入元素后,进行向上调整shiftUp(heap,heap->usedSize-1);
}int poll(MyHeap* heap){if(heap->usedSize>0){int ret=heap->arr[0];heap->arr[0]=heap->arr[heap->usedSize-1];//向下调整shiftDown(heap,0);(heap->usedSize)--;return ret;}else{printf("Heap is empty.");exit(1);}}int peek(MyHeap* heap){if(heap->usedSize>0){return heap->arr[0];}else{printf("Heap is empty.");exit(1);}
}int size(MyHeap* heap){return heap->usedSize;
}
二、使用堆进行排序
void HeapSort(int* arr,int len){MyHeap heap;//初始化堆的数据InitHeap(&heap,arr,len,len);//构建大顶堆CreateHeap(&heap);//对于n个元素,要进行poll操作n-1次for(int i=1;i<len;i++){arr[len-i]=poll(&heap);}arr[0]=peek(&heap);
}
交换排序
冒泡排序
void Bubble(int* arr,int n){int i,j,temp;//i控制轮数,每次会将一个大的元素,只需要移动n-1个元素之后,整个序列就有序了for(i=0;i<n-1;i++){int flag=1;for(j=0;j<n-1-i;j++){if(arr[j]>arr[j+1]){temp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;flag=0;}}if(flag==1){//表明所有元素有序break;}}
}