常用排序算法总结：选择法、冒泡法、直接插入法、希尔算法、快速算法、归并算法
本文总结了六种排序算法，分别是：选择法、冒泡法、直接插入法、希尔算法、快速算法、归并算法。
一、选择法排序
/*
选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。
*/
/*
第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；
第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；
以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，
使有序序列不断增长直到全部排序完毕。所以只会循环n-1次。
*/
template<class T>
void SelectSort(T *array, const int len)
{
//T temp = 0;
for (int i = 0; i < len - 1; i++)
{
int index_min = i;//假设待排序列中的第一个当做最小的，然后在待排序列中找到最小的
for (int j = i + 1; j < len; j++) //从第i个元素的后面一个元素开始找剩余的序列中最小的值的下标。
{
if (array[j] < array[index_min])
{
index_min = j;//找到新的最小的元素了
}
}
if (index_min != i)//若无序区第一个元素不是无序区中最小元素，则进行交换
{
array[index_min] = array[index_min] ^ array[i];
array[i] = array[index_min] ^ array[i];
array[index_min] = array[index_min] ^ array[i];
/*两种数据交换方式，第二种需要在前面定义一个缓存temp
//temp = array[index];
//array[index] = array[i];
//array[i] = temp;
*/
}
}
} 二、冒泡法排序：
/*
依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。
- 第一趟比较完成后，最后一个数一定是数组中最大的一个数，所以第二趟比较的时候最后一个数不参与比较；
- 第二趟比较完成后，倒数第二个数也一定是数组中第二大的数，所以第三趟比较的时候最后两个数不参与比较；
- 依次类推，每一趟比较次数-1；
*/
template<class T>
void BubbleSort(T *array, const int len)
{
T temp = 0;
for (int i = 0; i < len - 1; ++i)
{
int flag = 0;
for (int j = 0; j < len - 1 - i; ++j)
{
if (array[j] >= array[j + 1])
{
flag = 1;
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
if (flag == 0)
{
return;
}
}
} 三、直接插入法排序：
/*
在排序之前我们需要搞清一个思路，新插入一个数据的时候，排序过后的数组都是从小到大排列好的，所以我们需要从后往前查找，直到找到比我们要插入的数字还小的值。这个时候我们需要一个变量j作为标识
*/
template<class T>
void InsertSort(T * array, const int len)
{
T temp = 0;
for (int i = 1; i < len; i++)//还是n-1趟，只是这里从1开始，即第二个元素开始，前面的是有序的。
{
temp = array[i];//取出这个要和前面有序序列比较的元素。
int j = 0;
for (j = i - 1;j >= 0;j--)//这个元素的和前面有序序列比较，直到下标0
{
if (array[j] > temp)//将大于temp的数向后移动
{
array[j + 1] = array[j];
}
else
{
break;//不再比temp大了，就不移动了
}
}
//移动完，就插入元素
array[j + 1] = temp;//这里，因为j--，跳出循环时，j多减了一次
}
} 四、希尔排序算法：
/*
在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中
再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。
*/
template<class T>
void ShellSort(T *array, int len)
{
T temp;
int gap = len;////初始化划分增量
do
{
//业界统一实验的 平均最好情况 经过若干次后，收敛为1(跳出循环)
gap = gap / 3 + 1;
for (int i = gap; i < len; i += gap) //对每个划分进行 直接插入法排序
{
temp = array[i];//找到当前这个元素
int j = 0;
for (j = i - gap; j >= 0; j -= gap)//这个元素的和前面有序序列比较，直到下标0
{
if (array[j] > temp)//将大于temp的数向后移动
{
array[j + gap] = array[j];
}
else
{
break;//不再比temp大了，就不移动了
}
}
//移动完，就插入元素
array[j + gap] = temp;//这里，因为j-gap，跳出循环时，j多减了一次gap
}
} while (gap > 1);
} 五、快速排序算法：
/*
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
*/
template<class T>
void Quicksort(T *array, int low, int high)//high = len-1
{
if (low >= high)
{
return;//递归结束标志
}
int first = low;
int last = high;
int key = array[first];//用字表的第一个记录作为枢轴(区分小的分段和大的分段)
while (first < last)
{
while (first < last && array[last] >= key)
{
--last;
}
array[first] = array[last];/*将比key小的移到低端*/
while (first<last && array[first] <= key)
{
++first;
}
array[last] = array[first];/*将比key大的移到高端*/
}
array[first] = key;//重新确定枢轴的值，这里的first = last；(一定相等)//前面的枢轴值被覆盖了。
Quicksort(array, low, first - 1);//对左边的数据段排序
Quicksort(array, first + 1, high);//对右边的数据段排序
} 六、归并排序算法：
/*
归并排序法（Merge Sort，以下简称MS）是分治法思想运用的一个典范。其主要算法操作可以分为以下步骤：
Step 1：将n个元素分成两个含n/2元素的子序列
Step 2：用MS将两个子序列递归排序（最后可以将整个原序列分解成n个子序列）
Step 3：合并两个已排序好的序列（合并是该算法的核心）
*/
template<class T>
void Merge(T src[], T des[], int low, int mid, int high);
template<class T>
void MSort(T src[], T des[], int low, int high, int max);
template<class T>
void MergeSort(T *array, int len)// O(n*logn)
{
MSort(array, array, 0, len - 1, len);
}
//每次分为两路 当只剩下一个元素时，就不需要在划分
template<class T>
void MSort(T src[], T des[], int low, int high, int max)
{
if (low == high) //只有一个元素，不需要归并，结果赋给des[low]
{
des[low] = src[low];
}
else //如果多个元素，进行两路划分
{
int mid = (low + high) / 2;
T* space = new T[max];
//递归进行两路，两路的划分
//当剩下一个元素的时，递归划分结束，然后开始merge归并操作
if (space != nullptr)
{
MSort(src, space, low, mid, max);
MSort(src, space, mid + 1, high, max);
Merge(space, des, low, mid, high); //调用归并函数进行归并
}
delete[]space;
}
}
template<class T>
void Merge(T src[], T des[], int low, int mid, int high)
{
int i = low;
int j = mid + 1;
int k = low;
while ((i <= mid) && (j <= high)) //将小的放到目的地中
{
if (src[i] < src[j])
{
des[k++] = src[i++];
}
else
{
des[k++] = src[j++];
}
}
while (i <= mid) //若还剩几个尾部元素
{
des[k++] = src[i++];
}
while (j <= high) //若还剩几个尾部元素
{
des[k++] = src[j++];
}
} 七、主函数调用：
#include <iostream>
#include <string>
using namespace std;
template<class T>
void prinft_array(T &array)
{
for (int i = 0; i < sizeof(array)/sizeof(array[0]); i++)
{
cout << "array[" << i << "]:" << array[i] << endl;
}
}
int main(void)
{
int array1[] = { 10, 50, 60, 20, 12, 52, 62, 22, 14, 54, 64, 24 };
//char array2[] = { 'a', 'd', 'b', 'c'};
int len = sizeof(array1) / sizeof(array1[0]);
int low = 0;//指向开头
int high = len - 1;//指向末尾
cout << "排序之前" << endl;
prinft_array(array1);
//排序：
SelectSort(array1,len);
BubbleSort(array1, len);
InsertSort(array2, len);
ShellSort(array2, len);
Quicksort(array1, low, high);
MergeSort(array1, len);
cout << "排序之后" << endl;
prinft_array(array1);
system("pause");
return 0;
//自动排版：ctrl+K,ctrl+F
}
这是hr“不合适”的便捷语句
滴滴公司福利 235人发布