排序
冒泡排序
template <typename T>
void BubbleSort(vector<T>& list)
{
const int n = list.size();
for (int i = 0; i < n - 1; i++)
{
for (int j = n - 1; j > i; j--)
if (list[j] < list[j - 1])
swap(list[j], list[j - 1]);
}
}
插入排序
1. 直接插入排序
直接插入排序对本来已经大致有序的序列效率较高
template<typename T>
void InsertSort(vector<T>& list,int sizeOfSorted=1)
{
const int n = list.size();
for (int i = sizeOfSorted; i <= n-1; i++)
{
T temp = list[i];
int j = i - 1;
for ( j = i-1; j >= 0 && temp < list[j]; j--)
{
list[j+1] =list[j];
}
list[j+1] = temp;
}
}
1.折半插入排序
注意:
- while 循环的条件包括 =, 和
high = mid-1以及low = mid+1可以保证当循环结束时, 要插入的位置刚好是当前 low 的前一位. - 随着不断插入, low 和 high 每次循环时都要重新赋值.
template<typename T>
void BinaryInsertSort(vector<T>& list,const int sizeOfSorted=1)
{
const int n = list.size();
int low = 0;
int high = sizeOfSorted - 1;
int mid = 0;
for (int i = sizeOfSorted; i < n; i++)
{
T temp = list[i];
high = i - 1; low = 0;
while (low<=high)
{
mid = (low + high) / 2;
if (list[mid] > list[i])
high = mid-1;
else
low = mid+1;
}
for (int j = i; j > low; j--)
list[j] = list[j - 1];
list[low] = temp;
}
}
3. 希尔排序法
template<typename T>
void ShellInsertSort(vector<T>& list)
{
int gap = 0;
const int n = list.size();
for (gap = list.size() / 3; gap > 0; gap = gap / 3 + 1)
{
//各个子列轮流做直接插入, 将每个子列第零个元素设为基准
for (int i = gap; i < n; i++)
{
T temp = list[i];
int j = 0;
for ( j = i - gap; j >= 0 && temp < list[j] ; j -= gap)
{
list[j + gap] = list[j];
}
list[j + gap] = temp;
}
if (gap == 1) break;
}
}
快速排序法
通过一趟排序将序列分为左右两个子序列, 其中左序列所有的数据都小于右序列, 然后对这两个子序列进行快速排序,整个排序过程递归进行.
最好情况:元素均匀分布
最坏情况:基准为子序列最大或最小值
快速排序
//双指针
template <typename T>
int FindPos(vector<T>& list,const int left,const int right)
{
T base = list[left];
int smallerPos = left;
int greaterPos = right;
while ( smallerPos< greaterPos) {
while (list[greaterPos] >= base && smallerPos < greaterPos)
{
greaterPos--;
}
list[smallerPos] = list[greaterPos];
while (list[smallerPos] <= base && smallerPos < greaterPos)
{
smallerPos++;
}
list[greaterPos] = list[smallerPos];
}
list[smallerPos] = base;
return smallerPos;
}
//普通
template <typename T>
int FindPos(vector<T>& list, int left, int right)
{
T base = list[left];
int smallerPos =left;
for(int i=left+1;i<=right;i++)
{
if(list[i]<base)
{
smallerPos++;
if(i!=smallerPos)
swap(list[smallerPos],list[i]);
}
}
swap(list[left],list[smallerPos]);
return smallerPos;
}
template <typename T>
void QuickSort(vector<T>& list,int left,int right)
{
if (left < right) {
int pos = FindPos(list, left, right);
QuickSort(list, left, pos - 1);
QuickSort(list, pos + 1, right);
}
}
2.三路划分快速排序
template <typename T>
void QuickSort(vector<T>& list, int left, int right)
{
if (left >= right) return;
T base = list[left];
int lessPos = left;
int greaterPos = right + 1;
for (int i = left + 1; i < greaterPos; i++)
{
if (list[i] < base)
swap(list[++lessPos], list[i]);
else if (list[i] > base)
{
swap(list[i], list[--greaterPos]);
i--;
}
}
swap(list[left], list[lessPos]);
QuickSort(list, left, lessPos - 1);
QuickSort(list, greaterPos, right);
}
选择排序
1. 直接选择
template<typename T>
void selectSort(vector<T>& list)
{
for (int i = 0; i < list.size(); i++)
{
int indexOfmin = i;
int j;
for (j = i + 1; j < list.size(); j++)
{
if (list[j] < list[indexOfmin]) indexOfmin = j;
}
swap(list[i], list[indexOfmin]);
}
}
2.堆排序
#pragma once
#include <iostream>
#include <vector>
//第二个模板参数是比较器
using std::vector;
template <typename _Ty, typename _Com>
class priorityQueue
{
public:
priorityQueue() {}
priorityQueue(vector<_Ty>& arrays) :heap(arrays),start(0),end(arrays.size()-1)
{
siftDown();
}
priorityQueue( vector<_Ty>& arrays,int start,int end) :heap(arrays), start(start), end(end)
{
siftDown();
}
~priorityQueue() {}
void pop();
void push(const _Ty& item);
_Ty& top() { return heap[0]; };
protected:
private:
void siftDown(int startSift=-1);
void siftUp();
vector<_Ty>& heap;
int start;//起始位置下标
int end;//结束位置下标
};
template <typename _Ty, typename _Com>
void priorityQueue<_Ty, _Com>::push(const _Ty& item)
{
heap.push_back(item);
siftUp();
}
template <typename _Ty, typename _Com>
void priorityQueue<_Ty, _Com>::siftDown(int startSift)
{
//i,j 为偏移索引, start, end, startSift, endSift 为实际索引
if (start>=end)
{
return;
}
_Com comparator;
if (startSift == -1)
{
startSift = (end-start-1)/2+start;
}
for (size_t endSift = end; startSift-start >= 0; startSift--)
{
size_t i = startSift-start;
size_t j = 2 * i + 1;//i 的左孩子
_Ty temp = heap[i+start];
while (j+start <= endSift) {
if (j+start < endSift && comparator(heap[j+start], heap[j + 1+ start]))
j++;//j 指向更小的那个孩子
if (comparator(temp, heap[j+ start]))
{
heap[i+ start] = heap[j+ start];
i = j;
j = 2 * i + 1;
}
else
break;
}
heap[i+ start] = temp;
}
}
template <typename _Ty, typename _Com>
void priorityQueue<_Ty, _Com>::siftUp()
{
_Com com();
size_t i = end;
_Ty temp = heap[i];
for (size_t j = (i - 1) / 2; i > 0;)
{
if (j >= 0 && com(heap[j], temp))
{
heap[i] = heap[j];
i = j;
j = (i - 1) / 2;
}
else
break;
}
heap[i] = temp;
}
template <typename _Ty, typename _Com>
void priorityQueue<_Ty, _Com>::pop()
{
_Ty temp = heap[start];
heap[start] = heap[end];
heap[end] = temp;
end--;
siftDown(start);
}
//堆排序， 建立最大堆， 依次将根节点与最后一个元素交换， 然后再次调整为最大堆
template<class _Ty>
void HeapSort(vector<_Ty>& num, int start, int end)
{
auto comparator = [](_Ty a, _Ty b){return b >a; };
priorityQueue<_Ty, decltype(comparator)> maxHeap(num,start,end);
for (int i = start; i <= end; i++)
maxHeap.pop();
}
int main()
{
vector<int> num({ 9,8,7,6,5,4,3,2,1 });
HeapSort(num, 6, 8);
for (size_t i = 0; i < num.size(); i++)
{
std::cout << num[i] << " ";
}
}
基数排序
void radixSort(vector<int>& array)
{
vector<vector<int>> bucket(10);
int max=array[0];
for (int i = 1; i < array.size(); i++)
{
if (max < array[i]) max = array[i];
}
for (int round = 1; round <=max; round *= 10)
{
//进桶
for (int i = 0; i < array.size(); i++)
{
bucket[((array[i]) / round) % 10].push_back(array[i]);
}
int count = 0;
int i = 0;
while (count != array.size())
{
while (!bucket[i].empty())
{
array[count++] = bucket[i].front();
bucket[i].erase(bucket[i].begin());
}
i++;
}
}
}