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