# c++: 直接插入排序，冒泡排序，快速排序，堆排序和归并排序

3年前 阅读 937 点赞 3

### 直接插入排序

void InsertSort(int arr[], int len) {
int i, j;
int temp;
for (i = 1; i for (j = i - 1; j >= 0 && arr[j] > temp;j--)
arr[j + 1] = arr[j];
arr[j + 1] = temp;
}
}


void InsertSort(int arr[],int n){
for (int i =1;i for(int j = i;j > 0;--j){
if(arr[j] -1]){
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
}


void InsertSort2(vectorint> &num){
for(int i = 1;i for(int j = i;j > 0;--j){
if(num[j] 1]){
int temp = num[j];
num[j] = num[j-1];
num[j-1] = temp;
}
}
}
}


### 冒泡排序

void BubbleSort(int arr[], int n)
{
for (int i = 0; i 1; i++) {
for (int j = 0; j 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}


void BubbleSort(int arr[], int len){
int i,temp;
//记录位置，当前所在位置和最后发生交换的地方
int current,last = len - 1;
while(last > 0) {
for(i = current = 0;i if(arr[i] > arr[i+1]){
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
//记录当前的位置，如果没有发生交换current值即for循环初始化的0
current = i;
}
}
//若current = 0即已经没有可以交换的元素了，即已经有序了
last = current;
}
}


### 快速排序

void Qsort(std::vectorint> &set, int low, int high)
{
if(low int pivot = Partition(set, low, high);
Qsort(set, low, pivot - 1);
Qsort(set, pivot + 1, high);
}
}


int Partition(std::vectorint> &set, int low, int high)
{
int pivotkey=set.at(low);
while (low while (low set.at(high) set.at(low) = set.at(high);
while (low set.at(low) >= pivotkey)
low++;
set.at(high) = set.at(low);
}
set.at(low) = pivotkey;
return low;
}


void quickSort(std::vectorint> &s, int l, int r)
{
if(lint low=l;
int high=r;
int pivot = s[l];
while(lowwhile(low= pivot)
high--;
if(lowwhile(lowif(low1);
quickSort(s, low + 1, r);
}
}


### 堆排序

//堆排序
void HeapSort(int arr[],int len){
int i;
//初始化堆，从最后一个父节点开始
for(i = len/2 - 1; i >= 0; --i){
Heapify(arr,i,len);
}
//从堆中的取出最大的元素再调整堆
for(i = len - 1;i > 0;--i){
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
//调整成堆
Heapify(arr,0,i);
}
}


void Heapify(int arr[], int first, int end){
int father = first;
int son = father * 2 + 1;
while(son if(son + 1 1]) ++son;
//如果父节点大于子节点则表示调整完毕
if(arr[father] > arr[son]) break;
else {
//不然就交换父节点和子节点的元素
int temp = arr[father];
arr[father] = arr[son];
arr[son] = temp;
//父和子节点变成下一个要比较的位置
father = son;
son = 2 * father + 1;
}
}
}


### 归并排序

void Merge(int arr[], int reg[], int start, int end) {
if (start >= end)return;
int len = end - start, mid = (len >> 1) + start;

//分成两部分
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
//然后合并
Merge(arr, reg, start1, end1);
Merge(arr, reg, start2, end2);

int k = start;
//两个序列一一比较,哪的序列的元素小就放进reg序列里面,然后位置+1再与另一个序列原来位置的元素比较
//如此反复,可以把两个有序的序列合并成一个有序的序列
while (start1 //然后这里是分情况,如果arr2序列的已经全部都放进reg序列了然后跳出了循环
//那就表示arr序列还有更大的元素(一个或多个)没有放进reg序列,所以这一步就是接着放
while (start1 //这一步和上面一样
while (start2 //把已经有序的reg序列放回arr序列中
for (k = start; k void MergeSort(int arr[], const int len) {
//创建一个同样长度的序列,用于临时存放
int  reg[len];
Merge(arr, reg, 0, len - 1);
}