排序算法总结源代码

这里罗列了很多的排序算法,希望对大家有用!

shell排序

#include <iostream>

using namespace std;

/*

shell排序是对插入排序的一个改装，它每次排序把序列的元素按照某个增量分成几个子序列，对这几

个子序列进行插入排序，然后不断的缩小增量扩大每个子序列的元素数量，直到增量为一的时候子序列

就和原先的待排列序列一样了，此时只需要做少量的比较和移动就可以完成对序列的排序了。

*/

template<typename T>

void ShellSort(T array[], int length)

{

T temp;

// 增量从数组长度的一半开始,每次减小一倍

for (int increment = length / 2; increment > 0; increment /= 2)

{

for (int indexI = increment; indexI < length; ++indexI)

{

temp = array[indexI];

}

} } // 对一组增量为increment的元素进行插入排序 int indexJ; for (indexJ = indexI; indexJ >= increment; indexJ -= increment) { // 把i之前大于array[i]的数据向后移动 if (temp < array[indexJ - increment]) { array[indexJ] = array[indexJ - increment]; } else { break; } } // 在合适位置安放当前元素 array[indexJ] = temp;

这里罗列了很多的排序算法,希望对大家有用!

int main()

{

int array[6] = {2, 8, 6, 7, 5, 4};

ShellSort(array, 6);

for (int index = 0; index != 6; ++index)

{

cout<<array[index]<<" ";

}

cout<<endl;

}

插入排序

#include <iostream>

using namespace std;

/*

插入排序是最简单最直观的排序算法了，它的依据是：遍历到第N个元素的时候前面的N-1个元素已经是排

序好的了，那么就查找前面的N-1个元素把这第N个元素放在合适的位置，如此下去直到遍历完序列的元素

为止算法的复杂度也是简单的，排序第一个需要1的复杂度，排序第二个需要2的复杂度，因此整个的复杂

度就是1 + 2 + 3 + …… + N = O（N ^ 2）的复杂度。

*/

template<typename T>

void InsertSort(T array[], int length)

{

T key;

for (int indexI = 1; indexI < length; ++indexI)

{

key = array[indexI];

// 把i之前大于array[i]的数据向后移动

int indexJ;

for (indexJ = indexI - 1; indexJ >= 0 && array[indexJ] > key; --indexJ)

{

array[indexJ + 1] = array[indexJ];

}

// 在合适位置安放当前元素

array[indexJ + 1] = key;

}

}

这里罗列了很多的排序算法,希望对大家有用!

int main()

{

int array[6] = {2, 8, 6, 7, 3, 4};

InsertSort(array, 6);

for (int index = 0; index != 6; ++index)

{

cout<<array[index]<<" ";

}

cout<<endl;

}

堆排序

#include <iostream>

using namespace std;

/*

1 堆排序

2 (1)用大根堆排序的基本思想

3 ① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区

4 ② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换， 5 由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key

6 ③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。 7 然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换， 8 由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n- 2].keys≤R[n-1..n].keys，

9 同样要将R[1..n-2]调整为堆。

10 ……

11 直到无序区只有一个元素为止。

12 (2)大根堆排序算法的基本操作：

13 ① 初始化操作：将R[1..n]构造为初始堆；

14 ② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。

15 注意：

16 ①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。 17 ②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。

18 堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前， 19 且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。

20 */

void HeapAdjust(int SortData[],int StartIndex, int Length)

{

while(2*StartIndex+1 < Length)

这里罗列了很多的排序算法,希望对大家有用!

int MinChildrenIndex = 2*StartIndex+1 ; if(2*StartIndex+2 < Length ) { //比较左子树和右子树，记录最大值的Index if(SortData[2*StartIndex+1]<SortData[2*StartIndex+2]) { MinChildrenIndex = 2*StartIndex+2; } } if(SortData[StartIndex] < SortData[MinChildrenIndex]) { //交换i与MinChildrenIndex的数据 int tmpData =SortData[StartIndex]; SortData[StartIndex] =SortData[MinChildrenIndex]; SortData[MinChildrenIndex] =tmpData;

//堆被破坏，需要重新调整

StartIndex = MinChildrenIndex ;

}

else

{

//比较左右孩子均大则堆未破坏，不再需要调整

break;

}

}

return;

}

//堆排序

void HeapSortData(int SortData[], int Length)

{

int i=0;

//将Hr[0,Lenght-1]建成大根堆

for (i=Length/2-1; i>=0; i--)

{

HeapAdjust(SortData, i, Length);

}

for (i=Length-1; i>0; i--)

{

//与最后一个记录交换

int tmpData =SortData[0];

SortData[0] =SortData[i];

这里罗列了很多的排序算法,希望对大家有用!

SortData[i] =tmpData;

//将H.r[0..i]重新调整为大根堆

HeapAdjust(SortData, 0, i);

}

return;

}

int main()

{

int array[6] = {10, 15, 56, 25, 30, 70};

HeapSortData(array, 6);

for (int index = 0; index != 6; ++index)

{

cout<<array[index]<<" ";

}

cout<<endl;

}

归并排序

#include <iostream>

using namespace std;

/*

归并排序的算法思想：把待排序序列分成相同大小的两个部分，依次对这两部分进行归并排序，

完毕之后再按照顺序进行合并。

*/

// 归并排序中的合并算法

template<typename T>

void Merge(T array[], int start, int mid, int end)

{

T temp1[10], temp2[10];

int n1, n2;

n1 = mid - start + 1;

n2 = end - mid;

// 拷贝前半部分数组

for (int i = 0; i < n1; i++)

{

temp1[i] = array[start + i];

}

// 拷贝后半部分数组

这里罗列了很多的排序算法,希望对大家有用!

}

{ temp2[i] = array[mid + i + 1]; } // 把后面的元素设置的很大 temp1[n1] = temp2[n2] = 1000; // 逐个扫描两部分数组然后放到相应的位置去 for (int k = start, i = 0, j = 0; k <= end; k++) { if (temp1[i] <= temp2[j]) { array[k] = temp1[i]; i++; } else { array[k] = temp2[j]; j++; } }

// 归并排序

template<typename T>

void MergeSort(T array[], int start, int end)

{

if (start < end)

{

int nArea;

nArea = (end + start) / 2;

// 对前半部分进行排序 MergeSort(array, start, nArea);

// 对后半部分进行排序

MergeSort(array, nArea + 1, end);

// 合并前后两部分

Merge(array, start, nArea, end);

}

}

int main()

{

int array[6] = {2, 8, 6, 10, 5, 4};

MergeSort(array, 0, 5);

for (int index = 0; index != 6; ++index)

这里罗列了很多的排序算法,希望对大家有用!

}

cout<<array[index]<<" "; } cout<<endl;

快速排序

#include <iostream>

using namespace std;

/*

快速排序的算法思想： 选定一个枢纽元素，对待排序序列进行分割，分割之后的序列一个部分小于枢

纽元素，一个部分大于枢纽元素，再对这两个分割好的子序列进行上述的过程。 */

template<typename T>

void Swap(T *a, T *b)

{

T temp;

temp = * a;

* a = * b;

* b = temp;

}

// 对一个给定范围的子序列选定一个枢纽元素,执行完函数之后返回分割元素所在的位置, // 在分割元素之前的元素都小于枢纽元素,在它后面的元素都大于这个元素

template<typename T>

int Partition(T array[], int low, int high)

{

// 采用子序列的第一个元素为枢纽元素 int pivot = array[low]; while (low < high) { // 从后往前在后半部分中寻找第一个小于枢纽元素的元素 while (low < high && array[high] >= pivot) { --high; } // 将这个比枢纽元素小的元素交换到前半部分 Swap(&array[low], &array[high]);

这里罗列了很多的排序算法,希望对大家有用!

}

} // 从前往后在前半部分中寻找第一个大于枢纽元素的元素 while (low < high && array[low] <= pivot) { ++low; } // 将这个比枢纽元素大的元素交换到后半部分 Swap(&array[low], &array[high]); // 返回枢纽元素所在的位置 return low;

// 快速排序

template<typename T>

void QuickSort(T array[], int low, int high)

{

if (low < high)

{

int n = Partition(array, low, high);

QuickSort(array, low, n);

QuickSort(array, n + 1, high);

}

}

int main()

{

int array[6] = {2, 8, 6, 7, 3, 4};

QuickSort(array, 0, 5);

for (int index = 0; index != 6; ++index)

{

cout<<array[index]<<" ";

}

cout<<endl;

}

冒泡排序

#include <iostream>

using namespace std;

template<typename T>

void Swap(T *a, T *b)

{

T temp;

这里罗列了很多的排序算法,希望对大家有用!

}

* a = * b; * b = temp;

// 冒泡排序

template<typename T>

void BubbleSort(T array[], int length)

{

//记录一次遍历中是否有元素的交换

for (int indexI = 0; indexI < length; ++indexI)

{

int indexJ;

for (int indexJ = indexI + 1; indexJ < length; ++indexJ)

{

if (array[indexJ] < array[indexI])

{

Swap(&array[indexJ], & array[indexI]);

}

}

}

}

int main()

{

int array[6] = {2, 8, 6, 9, 5, 4};

BubbleSort(array, 6);

for (int index = 0; index != 6; ++index)

{

cout<<array[index]<<" ";

}

cout<<endl;

}

选择排序

#include <iostream>

using namespace std;

/*

将序列划分为无序和有序区，寻找无序区中的最小值和无序区的首元素交换，有序区扩大一个，

循环最终完成全部排序。

这里罗列了很多的排序算法,希望对大家有用!

template<typename T>

void SelectSort(T array[], int length)

{

int indexI, indexJ, indexK;//分别为有序区，无序区，无序区最小元素指针

for (indexI = 0; indexI < length; ++indexI)

{

indexK = indexI;

for (indexJ = indexI + 1; indexJ < length; ++indexJ)

{

if (array[indexJ] < array[indexK])

{

indexK = indexJ;

}

}

if (indexK != indexI)//若发现最小元素，则移动到有序区

{

T temp = array[indexK];

array[indexK] = array[indexI];

array[indexI] = temp;

}

}

}

int main()

{

int array[6] = {2, 8, 6, 7, 3, 4};

SelectSort(array,6);

for (int index = 0; index != 6; ++index)

{

cout<<array[index]<<" ";

}

cout<<endl;

}

基数排序

如果有相同基数的数,判断存储该基数的结构体内的next指针是否为空,为空就分配空间,存储数据,不为空表明这里已经存储了一个相同基数的数,所以递归回去再判断...,如此依序形成一个具有相同基数的数据链;读取的时候则先判断指针是否存在,存在就读出其中的数据,再读下一个指针...一直到指针为空,说明该数据链上的数据已全部读出,再取下一个数组元素...

本文来源：https://www.bwwdw.com/article/cbv4.html