C++选择排序插入排序希尔排序快排归并排及大小根堆实现优先级队列-智慧文博士

1.选择排序

(1)选择排序的实现

void ChoiceSort(int arr[], int size) { for (int i = 0; i < size - 1; i++) { int min = arr[i]; int k = i; // 记录最小值下标 for (int j = 1 + i; j < size; j++) { if (arr[j] < min) { k = j; min = arr[j]; } } if (k != i) { int tmp = arr[i]; arr[i] = arr[k]; arr[k] = tmp; } } }

这里k用来记录最小值的下标。

(2)相关知识

特点：每次选取元素中的最小值与当前元素进行交换。

缺点：相比冒泡排序交换的次数减少了，但是比较的次数仍然很多。

选择排序的平均时间复杂度是O(n*n),最好时间复杂度是O(n*n),最坏时间复杂度是O(n*n),空间复杂度O(1),稳定性(不稳定)

2.插入排序

(1)插入排序的实现

void InsertSort(int arr[], int size) { for (int i = 1; i < size; i++) { int val = arr[i]; int j = i - 1; for (; j >= 0; j--) { if (arr[j] <= val) { break; } arr[j + 1] = arr[j]; } arr[j + 1] = val; } }

(2)相关知识

特点：从第二个元素开始把前面的序列当成有序的，然后找到合适的位置进行插入。

优点：插入排序是普通排序里面效率最高的，在数据本身趋于有序的情况下插入排序是所有排序算法中效率最高的。

插入排序的平均时间复杂度O(n*n),最好时间复杂度O(n),最坏时间复杂度O(n*n),空间复杂度O(1),稳定性(稳定)

3.希尔排序

(1)希尔排序的实现

void ShellSort(int arr[], int size) { for (int gap = size; gap > 0; gap /= 2) { for (int i = gap; i < size; i++) { int val = arr[i]; int j = i - gap; for (; j >= 0; j-=gap) { if (arr[j] <= val) { break; } arr[j + gap] = arr[j]; } arr[j + gap] = val; } } }

(2)相关知识

特点:可以看作是多路的插入排序，每组的序列逐渐趋于有序，整体的序列也逐渐趋于有序，插入排序的完美体现。

希尔排序的平均时间复杂度O(n^1.3),最好时间复杂度O(n),最坏时间复杂度O(n*n),空间复杂度O(1),稳定性(不稳定)

4.快速排序

(1)快速排序的实现

//快排分割处理函数 int PartAction(int arr[],int l,int r) { //确定基准值 int val = arr[l]; //分割处理 while(l < r) { //r从右边找到第一个小于等于val的值放到l的位置，l++ while(l < r && arr[r] > val) { r --; } if(l < r) { arr[l] = arr[r]; l++; } //l从左边找到一个大于等于val的值放到r的位置上，r-- while(l < r && arr[l] < val) { l ++; } if(l < r) { arr[r] = arr[l]; r--; } } arr[l] = val; return l; } //快速排序的递归接口 void QuickSort(int arr[],int begin,int end) { //递归结束条件 if(begin >= end) { return ; } //快排分割函数 int pos = PartAction(arr,begin,end); //基准数的左边和右边再进行快排处理 QuickSort(arr,begin,pos-1); QuickSort(arr,pos+1,end); } //快速排序的递归实现 void QuickSort(int arr[],int size) { QuickSort(arr,0,size-1); }

(2)相关知识

特点：选取基准数，将小于基准数的值放到基准数的左边，大于基准数的放到基准数的右边，采用“分治思想”处理剩余的序列元素直到整个序列变成有序序列。

优化点：1.结合插入排序，当序列数据量小于某个值是采用插入排序进行排序。

2.采用”三数取中法”来进行基准数的选取。

3.随机数取基准数法

快速排序的平均时间复杂度为O(nlogn),最坏时间复杂度O(n*n),最好时间复杂度O(nlogn),空间复杂符O(logn)到O(n).稳定性(不稳定)。

5.归并排序

(1)归并排序的实现

//归并排序的排序接口 void Merge(int arr[],int l,int m,int r) { int *p = new int[r-l+1]; int pi = 0; int i = l; int j = m+1; while(i <= m && j <= r) { if(arr[i] <= arr[j]) { p[pi++] = arr[i++]; } else { p[pi++] = arr[j++]; } } while(i <= m) { p[pi++] = arr[i++]; } while(j <= r) { p[pi++] = arr[j++]; } for(i=l,j=0;i<=r;i++,j++) { arr[i] = p[j]; } delete p; } //归并排序的递归接口 void MergeSort(int arr[],int begin,int end) { //递归的结束条件 if(begin >= end) { return ; } //讲数组划分再进行递 int mid = (begin + end)/2; MergeSort(arr,begin,mid); MergeSort(arr,mid+1,end); //在归的过程中进行排序,将两个小段有序数组合成一个大段有序数组 Merge(arr,begin,mid,end); } //归并排序的实现 void MergeSort(int arr[],int size) { MergeSort(arr,0,size-1); }

(2)相关知识

特点：采用“分治思想”，先将序列进行划分，再进行合并排序

归并排序的平均时间复杂度O(nlogn),最坏时间复杂度O(nlogn),最好时间复杂度O(nlogn),空间复杂度O(n),稳定性(稳定)。

6.大小根堆优先级队列

(1)大小根堆优先级队列的实现

class PriorityQueue { public: using Comp = function<bool(int,int)>; PriorityQueue(int cap = 20,Comp comp = greater<int>()) :size_(0) ,cap_(cap) ,comp_(comp) { que_ = new int[cap_]; } PriorityQueue(Comp comp) :comp_(comp) ,cap_(20) ,size_(0) { que_ = new int[cap_]; } ~PriorityQueue() { delete []que_; que_ = nullptr; } //入堆 void push(int val) { if(size_ == cap_) { int *p = new int[cap_*2]; memcpy(p,que_,size_*sizeof(int)); delete []que_; que_ = p; cap_ *= 2; } if(size_ == 0) { que_[size_] = val; } else { //进行入堆上浮操作 siftUp(size_,val); } size_ ++; } //出堆 void pop() { if(size_ == 0) { throw "PriorityQueue is empty"; } size_ --; if(size_ == 0) { return; } else { //进行一个出堆下沉操作 siftDown(0,size_); } } //获取堆顶元素 int top() { if(size_ == 0) { throw "PriorityQueue is empty!"; } return que_[0]; } //判空 bool empty() { return size_ == 0; } //获取有效元素个数 int size() { return size_; } private: //入堆上浮操作 void siftUp(int i,int val) { while(i > 0) { //与当前父节点进行大小对比 int father = (i-1)/2; if(comp_(val,que_[father])) //注意与父节点比较的值是当前要入堆的值 { que_[i] = que_[father]; i = father; } else { break; } } que_[i] = val; } //出堆下沉操作 void siftDown(int i,int size) { while(i <= (size-2)/2) { int child = 2*i+1; if(child+1<size_ && comp_(que_[child+1],que_[child])) { child = child +1; } if(comp_(que_[child],que_[size])) { que_[i] = que_[child]; i = child; } else { break; } } que_[i] = que_[size]; } int *que_; int size_; int cap_; Comp comp_; };

在进行入堆的上浮和出堆的下沉操作时，对于和父子节点比较的值一个是要入堆的值，一个是数组最后一个元素的值。