本文是看了多个网页，不同的人写的关于排序算法的讲解和代码后整理的，因为如果公布这篇文章时如果选转载，就要写出原文链接，但是原文有很多，所以我写的是原创，但下面会详细写出一些参考链接，转载的部分也会详细说明并附上原文链接，不喜勿喷，谢谢！

【1 选择排序】

【排序思路：】从全部序列中选取最小的，与第0个元素交换，然后从第1个元素往后找出最小的，与第一个元素交换，再从第2个元素往后选取最小的，与第2个元素交换，直到选取最后一个元素。

void selection_sort(int arr[], int len)
{
for (int i = 0 ; i < len - 1 ; i++)
{
int min = i;
for (int j = i + 1; j < len; j++)
if (arr[j] < arr[min])
min = j;
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}

无论如何都要完整地执行内外两重循环，故最好、最差和平均时间复杂度都是O(n2)，不需要额外空间。选择排序是不稳定的。（下面的关于时间复杂度和稳定性这块就是从下面的参考链接中摘过来的了，不懂为什么选择排序是不稳定的，有懂的可以解释一下？）

【2 冒泡排序】

【排序思路：】从第n-1个元素到第0个元素遍历，若后面一个元素小于前面一个元素，则交换两个元素，这样可将整个序列中最小的元素冒泡到0的位置，然后再从第n-1个到第1个遍历，如此往复，直到只剩一个元素。

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

在网上看到很多人都是先从第0个元素到第n-1个元素遍历，若前面一个元素大于后面一个元素，则交换两个元素，这样可将整个序列中最大的元素冒泡到最后，然后再从第0个到第n-2遍历，如此往复，直到只剩一个元素。

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

【3 插入排序】

【排序思路：】分别将第1到第n-1个元素插入到前面已经排好序的序列的合适位置

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

【4 希尔排序】

【排序思路：】希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

void shell_sort(int arr[], int len)
{
int gap, i, j;
int temp;
for (gap = len/2; gap > 0; gap = gap/2)
for (i = gap; i < len; i++)
{
temp = arr[i];
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
arr[j + gap] = arr[j];
arr[j + gap] = temp;
}
}

【5 归并排序】

【排序思路：】利用二分的特性，将序列分成两个子序列进行排序，将排序后的两个子序列归并（合并），当序列的长度为2时，它的两个子序列长度为1，即视为有序，可直接合并，即达到归并排序的最小子状态。

//归并排序,迭代法
int min(int x, int y)
{
return x < y ? x : y;
}
void merge_sort1(int arr[], int len)
{
int* b = new int[len];
for (int seg = 1; seg < len; seg += seg)
{
for (int start = 0; start < len; start += seg + seg)
{
int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2)
b[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
while (start1 < end1)
b[k++] = arr[start1++];
while (start2 < end2)
b[k++] = arr[start2++];
}
int* temp = arr;
//下面这三句代码主要作用是将b的内容给arr，不能直接用复制的方式arr = b;这样只能把arr的地址变为b地址，那下面b变即arr变，就乱了
arr = b;
//这三句可以用for (int i=0;i<len;i++) arr[i] = b[i];代替，是一样的效果
b = temp;
}
delete []b;
}
//归并排序,递归法
void merge_sort_recursive(int arr[], int reg[], int start, int end)
{
if (start >= end)
return;
int len = end - start, mid = (len >> 1) + start;
//(len >> 1)就是len/2的意思
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2)
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
while (start1 <= end1)
reg[k++] = arr[start1++];
while (start2 <= end2)
reg[k++] = arr[start2++];
for (k = start; k <= end; k++)
arr[k] = reg[k];
}
void merge_sort2(int arr[], const int len)
{
int* reg = new int[len];
merge_sort_recursive(arr, reg, 0, len - 1);
delete []reg;
}

【6 快速排序】

【递归实现：】此部分为转载，下面附有原文链接

快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序是一种不稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

该方法的基本思想是：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

以一个数组作为示例，取区间第一个数为基准数。

初始时，i = 0;  j =9;   X = a[i] = 72

由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。

从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8];i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3];j--;

数组变为：

 i = 3;   j =7;   X=72

再重复上面的步骤，先从后向前找，再从前向后找。

从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;

从i开始向后找，当i=5时，由于i==j退出。

此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。

数组变为：

可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

对挖坑填数进行总结

1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。

2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。

3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。

4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

代码如下：

///快速排序，递归法
void quick_sort_recursive(int s[], int l, int r)
{
if (l< r)
{
int i = l, j = r, x = s[l];
while (i < j)
{
while(i < j && s[j]>= x) // 从右向左找第一个小于x的数
j--;
if(i < j)
s[i++] = s[j];
while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数
i++;
if(i < j)
s[j--] = s[i];
}
s[i] = x;
quick_sort_recursive(s, l, i - 1); // 递归调用
quick_sort_recursive(s, i + 1, r);
}
}
void quick_sort2(int arr[], int len)
{
quick_sort_recursive(arr,0,len-1);
}

参考链接：https://www.jianshu.com/p/916b15eae350

                  https://www.runoob.com/cprogramming/c-sort-algorithm.html

                 快速排序递归实现的原文链接

最后

以上就是柔弱季节为你收集整理的排序算法【1 选择排序】【2 冒泡排序】【3 插入排序】【4 希尔排序】【5 归并排序】【6 快速排序】的全部内容，希望文章能够帮你解决排序算法【1 选择排序】【2 冒泡排序】【3 插入排序】【4 希尔排序】【5 归并排序】【6 快速排序】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。