# 七大常见排序，你究竟懂几个？（下）

1.冒泡排序

2.快速排序

3.归并排序

## 1、冒泡排序

代码：

``````#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//交换
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}

//冒泡排序
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n; j++)
{
int exchange = 0;
for (int i = 1; i < n - j; i++)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;//避免不必要的排序
}
}
if (exchange == 0)
{
break;
}
}
}
void PrintArray(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("n");
}

int main()
{
int a[] = { 7, 3, 2, 6, 8, 1, 9};
int size = sizeof(a) / sizeof(int);
BubbleSort(a, size);
PrintArray(a, size);
return 0;
}
``````

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定

## 2、快速排序

### 2.1挖坑法

考虑：快速排序什么情况下最坏了？当它有序时，时间复杂度为O(N^2)。

``````#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//交换
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//三数取中法
int GetMidIndex(int* a, int left, int right)
{
int mid = (left + right) >> 1;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
else // a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}

//快速排序之挖坑法
void QuickSort(int* a,int left,int right)
{
if (left >= right)
{
return;
}

int index = GetMidIndex(a, left, right);
Swap(&a[left], &a[index]);

int begin = left;
int end = right;
int key = a[begin];
int pivot = begin;
while (begin < end)
{
while (begin < end && a[end] >= key)
{
end--;
}
a[pivot] = a[end];
pivot = end;
while (begin < end && a[begin] <= key)
{
begin++;
}
a[pivot] = a[begin];
pivot = begin;
}
a[pivot] = key;

QuickSort(a, left, pivot - 1);
QuickSort(a, pivot + 1, right);

}
void PrintArray(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("n");
}

int main()
{
int a[] = { 7, 3, 2, 6, 8, 1, 9};
int size = sizeof(a) / sizeof(int);
QuickSort(a, 0, size - 1);
PrintArray(a, size);

return 0;
}``````

### 2.2左右指针法

``````#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//交换
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}

//三数取中法
int GetMidIndex(int* a, int left, int right)
{
int mid = (left + right) >> 1;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
else // a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}

//快速排序之左右指针法
void QuickSort2(int* a, int lefti, int righti)
{
if (lefti >= righti)
{
return;
}

int index = GetMidIndex(a, lefti, righti);
Swap(&a[lefti], &a[index]);

int left = lefti;
int right = righti;
int key = left;
while (left < right)
{
while (left < right && a[right] >= a[key])
{
--right;
}
while (left < right && a[left] <= a[key])
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[key], &a[left]);

QuickSort2(a, lefti, left-1);
QuickSort2(a, left+1, righti);
}
void PrintArray(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("n");
}

int main()
{
int a[] = { 7, 3, 2, 6, 8, 1, 9};
int size = sizeof(a) / sizeof(int);
QuickSort2(a, 0, size - 1);
PrintArray(a, size);
return 0;
}``````

### 2.3前后指针法

``````#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//交换
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}

//三数取中法
int GetMidIndex(int* a, int left, int right)
{
int mid = (left + right) >> 1;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right])
{
return left;
}
else
{
return right;
}
}
else // a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
//快速排序之前后指针法
void QuickSort3(int* a, int lefti, int righti)
{
if (lefti >= righti)
{
return;
}

int index = GetMidIndex(a, lefti, righti);
Swap(&a[lefti], &a[index]);

int after = lefti;
int front = lefti + 1;
int key = lefti;

while (front <= righti)
{
if (a[front] < a[key])
{
after++;
Swap(&a[front], &a[after]);
}
front++;
}
Swap(&a[after], &a[key]);
QuickSort3(a, lefti, after - 1);
QuickSort3(a, after + 1, righti);

}

void PrintArray(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("n");
}

int main()
{
int a[] = { 7, 3, 2, 6, 8, 1, 9};
int size = sizeof(a) / sizeof(int);
QuickSort3(a, 0, size - 1);
PrintArray(a, size);

return 0;
}``````

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定

### 3、归并排序

``````#include<stdlib.h>
#include<stdio.h>
//归并排序
void _MergeSort(int* a, int left, int right, int* tmp)
{
if (left >= right)
return;

int mid = (left + right) >> 1;
// 假设 [left, mid] [mid+1, right]有序，那么我们就可以归并了
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp);

// 归并
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}

while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}

while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}

// 拷贝回去
for (int i = left; i <= right; ++i)
{
a[i] = tmp[i];
}
}

void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}

void PrintArray(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("n");
}

int main()
{
MergeSort(a, size - 1);
PrintArray(a, size);
return 0;
}``````

归并排序的特性总结：

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问 题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定

排序算法复杂度及稳定性分析

THE END