常用排序算法总结及C源程序

*直接插入排序*/

/*思想：先将有序序列中的第1个元素看作是有序序列的子序列，然后从第2个记录开始逐个进行插入*/

/*直至整个序列变成按关键字非递减的有序序列为止。*/ void InsertSort(int *out, int *op, int length)

{

int i, j;

int data; memcpy(out, op, length * sizeof(int));

for(i = 1; i < length; i++)

{

data = out;

for(j = i-1; data < out[j] && j >=0; j--)

{

out[j+1] = out[j];

}

out[j+1] = data;

}

}

--------------------------------------------------------------------------------------------------------------------------------

/*折半插入排序*/

/*思想：与折半查找类似*/

void BInsertSort(int *out, int *op, int length) {

int low, mid, high;

int i, j, data;

memcpy(out, op, length * sizeof(int)); for(i = 1; i < length; i++)

{

data = out;

low = 0;

high = i - 1;

while(low <= high)

{

mid = (low+high) / 2;

if(data < out[mid])

high = mid - 1;

else

low = mid + 1;

}

for(j = i-1; j >= high+1; j--)

out[j+1] = out[j];

out[j+1] = data;

}

}

--------------------------------------------------------------------------------------------------------------------------------

/*冒泡算法*/

/*思想：*/

/*第一趟冒泡排序（比较第1个到第n个记录）：*/

/*首先比较第1个元素和第2个元素的大小，若第1个比第2个小，则交换他们的值*/

/*接着比较第2个元素和第3个元素的大小……直到第n-1和第n个元素*/

/*第二趟冒泡排序（比较第1个到第n-1个记录）*/

void BubbleSort(int *out, int *op, int length)

{

int i, j;

memcpy(out, op, length * sizeof(int));

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

{

for(j = 0; j < i; j++)

{

if(out[j] > out[j+1])

{

swap(out+j, out+j+1);

}

}

}

}

--------------------------------------------------------------------------------------------------------------------------------

/*快速排序，对冒泡排序的一种改进*/

/*思想：通过一趟排序，将待排记录分为独立的两部分，其中一部分记录的关键字均比另一部分的关键字小*/

/*则可对这两部分记录继续进行排序，以达到整个序列有序*/ /*一趟快速排序的做法*/

/*附设两个指针low,high，分别指向第1个记录和第n个记录，设关键字枢纽为pivokey,指向第一个记录*/

/*1.首先从high位置向前搜索，直到搜到比pivokey小的记录，与pivokey进行交换*/

/*2.从low位置向后搜索，知道搜到比pivokey大的记录，与pivokey进行交换*/

/*3.重复这两步，直到low = high为止*/

int Partition(int *out, int *op, int length, int low, int high) {

int pivokey;

memcpy(out, op, length * sizeof(int));

pivokey = out[low];

while(low < high)

{

while(out[high] > pivokey && low < high)

{

high--;

}

swap(out+high, &pivokey);

while(out[low] < pivokey && low < high)

{

low++;

}

swap(out+low, &pivokey);

}

return low;

}

//递归形式的快速排序算法

void QSort(int *out, int *op, int length, int low, int high)

{

int pivoloc;

memcpy(out, op, length * sizeof(int));

if(low < high)

{

pivoloc = Partition(out, op, length, low, high);

QSort(out, out, length, low, pivoloc-1);

QSort(out, out, length, pivoloc+1, high);

}

}

--------------------------------------------------------------------------------------------------------------------------------

/*

选择排序

思想：每一趟在n-i（i=0,1,...n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。

*/

/*

简单选择排序

思想：一趟简单选择排序的操作为：通过n-i-1次关键字之间的比较，从n-i个记录中选取关键字最小

的记录，并和第i（1<=i<=n）个记录交换。

*/

//从第i到第n个位置，找出n-i+1个记录中的最小值的位置。 int SelectMinKey(int *op, int length, int i)

{

int pos = i, j;

int min = op;

for(j = i + 1; j < length; j++)

{

if(op[j] < min)

{

min = op[j];

pos = j;

}

}

return pos;

}

//简单选择排序

void SelectSort(int *out, int *op, int length)

{

int i, j;

memcpy(out, op, length * sizeof(int));

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

{

j = SelectMinKey(out, length, i);

if(i != j)

{

swap(out+i, out+j);

}

}

}

--------------------------------------------------------------------------------------------------------------------------------

/*希尔排序，又称：缩小增量排序*/

/*思路：先将整个待排序列分为几个子序列，分别进行直接插入排序，待整个序列中的记录基本有序时*/

/*再对全体记录进行一次直接插入排序*/

void Shell(int *out, int *op, int length, int dk) //一趟希尔排序 {

//与直接插入排序相比，前后记录位置的增量为dk，而不是1 int i, j, data;

memcpy(out, op, length * sizeof(int));

for(i = dk; i < length; i++)

{

data = out;

for(j = i-dk; (data < out[j]) && j>=0; j=j-dk) {

out[j+dk] = out[j];

}

out[j+dk] = data;

}

}

//按增量序列dlta[0,...,t-1]对顺序表作希尔排序

void ShellSort(int *out, int *op, int *dlta, int t, int length) {

int k;

for(k = 0; k < t; k++)

{

Shell(out, op, length, dlta[k]);

}

}

 

第二篇：排序算法总结源代码

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];

}

// 拷贝后半部分数组

}

for (int i = 0; i < n2; 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;

}

temp = * a; * 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指针是否为空,为空就分配空间,存储数据,不为空表明这里已经存储了一个相同基数的数,所以递归回去再判断...,如此依序形成一个具有相同基数的数据链;读取的时候则先判断指针是否存在,存在就读出其中的数据,再读下一个指针...一直到指针为空,说明该数据链上的数据已全部读出,再取下一个数组元素...