几种常用的排序算法比较

[常用进程调度算法有哪些]先来先服务调度算法：当在作业（或进程）调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入队列的作业，将他们调入内存，为它们分配资源、创建进程，然后放入就绪...+阅读

几种常用的排序算法比较

排序，从小大，0坐标的在下面，即排序后小的在下面，大的在上面。1，冒泡Bubble：从第0个开始，一直往上，与相邻的元素比较，如果下面的大，则交换。Analysis:Implementation:void BubbleSort(int *pData, int iNum)2，插入Insertion：与打扑克牌时整理牌很想象，假定第一张牌是有序的，从第二张牌开始，拿出这张牌来，往下比较，如果有比这张牌大的，则把它拨到上一个位置，直到找到比手上的这张更小的（或到顶了），则把手上的这张牌插入到这张更小的牌的后面。Analysis:Implementation:void InsertionSort(int *list, int length) { int i, j, temp; for (i = 1; i { temp = list[i]; j = i - 1; while ((j >= 0) & (list[j] >temp)) { list[j+1] = list[j]; j--; } list[j+1] = temp; } }3，选择Selection：从所有元素中找到最小的放在0号位置，从其它元素（除了0号元素）中再找到最小的，放到1号位置，......。Analysis:Implementation:void SelectionSort(int data[], int count) { int i, j, min, temp; for (i = 0; i { /* find the minimum */ min = i; for (j = i+1; j { if (data[j] { min = j; } } /* swap data[i] and data[min] */ temp = data[i]; data[i] = data[min]; data[min] = temp; } }4，快速Quick：先拿出中间的元素来（值保存到temp里），设置两个索引（index or pointer），一个从0号位置开始往最大位置寻找比temp大的元素；一个从最大号位置开始往最小位置寻找比temp小的元素，找到了或到顶了，则将两个索引所指向的元素互换，如此一直寻找交换下去，直到两个索引交叉了位置，这个时候，从0号位置到第二个索引的所有元素就都比temp小，从第一个索引到最大位置的所有元素就都比temp大，这样就把所有元素分为了两块，然后采用前面的办法分别排序这两个部分。总的来说，就是随机找一个元素（通常是中间的元素），然后把小的放在它的左边，大的放右边，对左右两边的数据继续采用同样的办法。只是为了节省空间，上面采用了左右交换的方法来达到目的。Analysis:Implementation:void QuickSort(int *pData, int left, int right) { int i, j; int middle, iTemp; i = left; j = right; middle = pData[(left + right) / 2]； //求中间值 do { while ((pData[i] i++; while ((pData[j] >middle) & (j >left)） //从右扫描小于中值的数 j--; if (i { //交换 iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; i++; j--; } } while (i //当左边部分有值（left if(left QuickSort(pData, left, j)； //当右边部分有值（right>i），递归右半边 if(right >i) QuickSort(pData, i, right); }5，希尔Shell：是对Insertion Sort的一种改进，在Insertion Sort中，从第2个位置开始取出数据，每次都是与前一个（step/gap==1）进行比较。Shell Sort修改为，在开始时采用较大的步长step，从第step位置开始取数据，每次都与它的前step个位置上的数据进行比较（如果有8个数据，初始step==4，那么pos

(4)与pos(0)比较，pos(0)与pos(-4),pos

(5)与pos

(1),pos

(1)与pos(-3),...... pos

(7)与pos

(3),pos

(3)与pos(-1)），然后逐渐地减小step，直到step==1。step==1时，排序过程与Insertion Sort一样，但因为有前面的排序，这次排序将减少比较和交换的次数。Shell Sort的时间复杂度与步长step的选择有很大的关系。Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort,MergeSort,HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。Analysis:Implementation:template void ShellSort(RandomIter begin, RandomIter end, Compare cmp) { typedef typename std::iterator_traits::value_type value_type; typedef typename std::iterator_traits::difference_type diff_t; diff_t size = std::distance(begin, end); diff_t step = size / 2; while (step >= 1) { for (diff_t i = step; i { value_type key = *(begin+i); diff_t ins = i; // current position while (ins >= step & cmp(key, *(begin+ins-step))) { *(begin+ins) = *(begin+ins-step); ins -= step; } *(begin+ins) = key; } if(step == 2) step = 1; else step = static_cast(step / 2.2); } } template void ShellSort(RandomIter begin, RandomIter end) { typedef typename std::iterator_traits::value_type value_type; ShellSort(begin, end, std::less()); }6，归并Merge：先将所有数据分割成单个的元素，这个时候单个元素都是有序的，然后前后相邻的两个两两有序地合并，合并后的这两个数据再与后面的两个合并后的数据再次合并，充分前面的过程直到所有的数据都合并到一块。通常在合并的时候需要分配新的内存。Analysis:Implementation:void Merge(int array[], int low, int mid, int high) { int k; int *temp = (int *) malloc((high-low+1) * sizeof(int)）； //申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 int begin1 = low; int end1 = mid; int begin2 = mid + 1; int end2 = high; for (k = 0; begin1 { if(array[begin1] { temp[k] = array[begin1++]; } else { temp[k] = array[begin2++]; } } if(begin1 { memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int)); } if(begin2 { memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int)); } ...

选择排序法十个整数

展开全部

你这个就是冒泡啊。

冒泡排序：

#include ＂stdio.h＂

#include ＂conio.h＂

void printArray(int a[],int n)

{

int i;

for(i=0;i {

printf(＂%2d ＂,a[i]);

}

void bubblesort(int a[],int n)

{

int i,j,temp=0;

for(i=0;i {

for(j=n-1;j>i;j--)

{

if(a[j] {

temp=a[j];

a[j]=a[j-1];

a[j-1]=temp;

}

printf(＂\n第%i轮排序结果：\n＂,i);

printArray(a,10);

}

main()

{

int a[10]={22,8,21,3,7,5,13,0,4,9};

printf（＂排序前\n＂）;

printArray(a,10);

bubblesort(a,10);

printf(＂\n排序后\n＂);

printArray(a,10);

getch();

}

在C中有哪些排序法

本人学习数据结构时看到的不错的总结，共享一下了文件有一组记录组成，记录有若干数据项组成，唯一标识记录的数据项称关键字；排序是将文件按关键字的递增（减）顺序排列；排序文件中有相同的关键字时，若排序后相对次序保持不变的称稳定排序，否则称不稳定排序；在排序过程中，文件放在内存中处理不涉及数据的内、外存交换的称内部排序，反之称外部排序；排序算法的基本操作：1）比较关键字的大小；2）改变指向记录的指针或移动记录本身。评价排序方法的标准：1）执行时间；2）所需辅助空间，辅助空间为O

(1)称就地排序；另要注意算法的复杂程度。若关键字类型没有比较运算符，可事先定义宏或函数表示比较运算。 8.2插入排序 8.2.1直接插入排序实现过程： void insertsort(seqlist R) { int i, j; for(i=2;i if(R[i].key R[0]=R[i];j=i-1; do{R[j+1]=R[j];j--;} while(R[0].key R[j+1]=R[0]； } } 复制代码算法中引入监视哨R[0]的作用是：1)保存 R[i] 复制代码的副本；2）简化边界条件，防止循环下标越界。关键字比较次数最大为（n+2）(n-1)/2；记录移动次数最大为（n+4）(n-1)/2；算法的最好时间是O(n)；最坏时间是O(n^2)；平均时间是O(n^2)；是一种就地的稳定的排序； 8.2.2希尔排序实现过程：是将直接插入排序的间隔变为d。d的取值要注意：1）最后一次必为1;2）避免d值互为倍数；关键字比较次数最大为n^1.25；记录移动次数最大为1.6n^1.25；算法的平均时间是O(n^1.25)；是一种就地的不稳定的排序； 8.3交换排序 8.3.1冒泡排序实现过程：从下到上相邻两个比较，按小在上原则扫描一次，确定最小值，重复n-1次。关键字比较次数最小为n-

1、最大为n(n-1)/2；记录移动次数最小为0，最大为3n(n-1)/2；算法的最好时间是O(n)；最坏时间是O(n^2)；平均时间是O(n^2)；是一种就地的稳定的排序； 8.3.2快速排序实现过程：将第一个值作为基准，设置i,j指针交替从两头与基准比较，有交换后，交换j,i。i=j时确定基准，并以其为界限将序列分为两段。重复以上步骤。关键字比较次数最好为nlog2n+nC

(1)、最坏为n(n-1)/2；算法的最好时间是O(nlog2n)；最坏时间是O(n^2)；平均时间是O(nlog2n)；辅助空间为O(log2n)；是一种不稳定排序； 8.4选择排序 8.4.1直接选择排序实现过程：选择序列中最小的插入第一位，在剩余的序列中重复上一步，共重复n-1次。关键字比较次数为n(n-1)/2；记录移动次数最小为0，最大为3(n-1)；算法的最好时间是O(n^2)；最坏时间是O(n^2)；平均时间是O(n^2)；是一种就地的不稳定的排序； 8.4.2堆排序实现过程：把序列按层次填入完全二叉树，调整位置使双亲大于或小于孩子，建立初始大根或小根堆，调整树根与最后一个叶子的位置，排除该叶子重新调整位置。算法的最好时间是O(nlog2n)；最坏时间是O(nlog2n)；平均时间是O(nlog2n)；是一种就地的不稳定排序； 8.5归并排序实现过程：将初始序列分为2个一组，最后单数轮空，对每一组排序后作为一个单元，对2个单元排序，直到结束。算法的最好时间是O(nlog2n)；最坏时间是O(nlog2n)；平均时间是O(nlog2n)；辅助空间为O(n)；是一种稳定排序； 8.6分配排序 8.6.1箱排序实现过程：按关键字的取值范围确定箱子的个数，将序列按关键字放入箱中，输出非空箱的关键字。在桶内分配和收集，及对各桶进行插入排序的时间为O(n)，算法的期望时间是O(n)，最坏时间是O(n^2)。 8.6.2基数排序实现过程：按基数设置箱子，对关键字从低位到高位依次进行箱排序。算法的最好时间是O(d*n+d*rd)；最坏时间是O(d*n+d*rd)；平均时间是O(d*n+d*rd)；辅助空间O(n+rd)；是一种稳定排序； 8.7各种内部排序方法的比较和选择按平均时间复杂度分为： 1）平方阶排序：直接插入、直接选择、冒泡排序； 2）线性对数阶：快速排序、堆排序、归并排序； 3）指数阶：希尔排序； 4）线性阶：箱排序、基数排序。选择合适排序方法的因素：1）待排序的记录数；2）记录的大小；3）关键字的结构和初始状态；4）对稳定性的要求；5）语言工具的条件；6）存储结构；7）时间和辅助空间复杂度。结论： 1）若规模较小可采用直接插入或直接选择排序； 2）若文件初始状态基本有序可采用直接插入、冒泡或随机快速排序； 3）若规模较大可采用快速排序、堆排序或归并排序； 4）任何借助于比较的排序，至少需要O(nlog2n)的时间，箱排序和基数排序只适用于有明显结构特征的关键字； 5）有的语言没有提供指针及递归，使归并、快速、基数排序算法复杂； 6）记录规模较大时为避免大量移动记录可用链表作为存储结构，如插入、归并、基数排序，但快速、堆排序在链表上难以实现，可提取关键字建立索引表，然后对索引表排序。附二：第八章排序 ************************************************************************************* 记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字。排序是使文件中的记录按关键字递增（或递减）次序排列起来。·基本操作：比较关键字大小；改变指向记录的指针或移动记录。 ·存储结构：顺序结构、链表结构、索引结构。经...