快速排序
void QuickSort(vector<int>& data, int begin, int end){
if(begin < end){
int pivot = parition(data, begin, end);
QuickSort(data, begin, pivot - 1);
QucikSort(data, pivot + 1, end);
}
}
void parition(vector<int>& data, int begin, int end){
int pivot = data[begin];
while(begin < end){
while(begin < end && data[end] > pivot){
end--;
}
data[begin] = data[end];
while(begin < end && data[begin] < pivot){
begin++;
}
data[end] = data[begin];
}
data[begin] = pivot;
return pivot;
}
归并排序
void MergeSort(vector<int>& data, vector<int>& temp, int begin, int end){
if(begin < end){
int mid = (begin + end) / 2;
MergeSort(data, temp, begin, mid);
MergeSort(data, temp, mid + 1, end);
Merge(data, temp, begin, mid, end);
}
}
void Merge(vector<int>& data, vector<int>& temp, int begin, int mid, int end){
int i = begin;
int j = mid + 1;
int k = 0;
while(i <= mid && j <= end){
if(data[i] < data[j]){
temp[k++] = data[i++];
}else{
temp[k++] = data[j++];
}
}
while(i <= mid){
temp[k++] = data[i++];
}
while(j <= mid){
temp[k++] = data[j++];
}
k = 0;
while(begin <= end){
data[begin++] = temp[k++];
}
}
堆排序
void heapSort(vector<int>& data){
int size = data.size();
for(int i = size / 2 - 1; i >= 0; i--){
adjustHeap(data, i, size);
}
for(int i = size - 1; i > 0; i--){
swap(data[0], data[i]);
adjustHeap(data, 0, i); // 从0开始 重新对堆进行排序
}
}
// 从i的位置 往下查找 有没有比这个位置大的 如果有 就记录下来 最后替换
void adjustHeap(vector<int>& data, int i, int length){
int temp = data[i];
for(int k = 2 * i + 1; k < length; k = 2 * k + 1){
if(k + 1 < length && data[k] < data[k + 1]){
k++;
}
if(data[k] > temp){ // 从下面找一个最大的
datat[i] = data[k];
i = k;
}else{
break;
}
}
data[i] = temp;
}
希尔排序
void Sort(vector<int>& data){
int size = data.size();
// 增量gap，并逐步缩小增量
for(int gap = size / 2; gap > 0; gap--){
// 从第gap个元素，逐个对其所在组进行插入排序操作
for(int i = gap; i < size; i++){
int j = i;
while(j - gap >= 0 && array[j] < array[j - gap]){ // 对同组的元素 采用插入排序
swap(data[j], data[j - gap]);
j -= gap;
}
}
}
}
