数据结构排序算法

《数据结构排序算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、常见排序算法总结1.基木概念排序：是将一组数据元素按某种特定要求(升或降序)排列成有规律序列的过程。排序可以分为内部排序和外部排序两种：1).若整个排序过程不需要访问外存便能完成，则称此类排序为内部排序。2).若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，需要借助外存来完成，则称此类排序为外部排序。〃不涉及内外存交换就地排序：若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间为0(1),则称为就地排序。稳定性：假设在待排序的元素屮，存在两个或两个以上的元素具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元索的相对次序仍然不变，则

2、这种排序方法是稳定的。2.常见内部排序2.1交换排序交换排序的基本思想是两两比较待排序记录的关键字，若发牛:与排序要求相逆，则交换Z,反复进行，直到数据冇序。交换排序的主要方法有：冒泡排序和快速排序。1).冒泡排序a.算法思想已知一组无序数据元素P[n],需将按其关键字升序排列。第一趟对n个元索冒泡得到一个关键字最大的元索P[n-1],第二趟冒泡对个元素得到一个关键字最大的元素P[n-2],依次类推，直到数据有序。b.算法实现voidbuble(intarr[],intn){boolflag;//用于判断是否发生了交换inti;inttemp;〃临时变量〃反复多轮

3、，从小到大排序。do{〃一轮排序flag=false;〃反复比较所有相邻的元素，循环比较n-1次。for(i=1;ivn;i++){〃如來顺序不当，就交换他们。讦(arr[i]

4、一个元索P[x](通常选取首元索)作为基准，多次比较P[x]与具它元素并交换。直到当P[x]可以排在序列的第k位，并只使P[0]~P[k]中的每一个元素小于P[x],P[k+1]-P[n-1]中的每一个元素不小于P[x]时,交换P[x]和P[k]。再分别对P[0]~P[k・l]和P[k+1]-P[n-1]两组数据元素重复上述过程，直到数据有序。b.算法实现〃交换函数voidswap(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}〃快速排序voidqsort(intarr[],intn){inttemp;int*L,*R;i

5、f(nv二1)return;if(n==2){if(arr[l]arr&&*R>=temp)R~;if(L

6、排序插入排序的基本思想是每次将一个待排序的元素按其关键字的大小，插到前面的有序元素中，反复进行，直到数据有序。插入排序方法主要有：直接插入排序、折半插入排序和希尔排序。1).直接插入排序a.算法思想已知一组无序数据元索P[n],需将按其关键字升序排列。假设前面(n・l)(n>=2)个元素已经是排好顺序的，现在要把笫n个元素插到前面的冇序元素中，使得这n个元素也是冇序的，如此反复，直到数据冇序。其中查找插入位置时采用顺序查找。b.算法实现voidinsert(intarr[],intn){inti,j;inttemp;for(i=1;i

7、序,反复n-1次。if(arr[i]>=arr[i-l]){continue;}temp=arr[i];//另存一份for(j=i;j>0&&arr[j-1]>temp;j-){arr[j]=arr[j-1];}arr[j]=temp;//插入备份}}注：直接插入排序算法是稳定的，吋间复杂度是0(22)。2).折半插入排序a.算法思想已知一组无序数据元素P[n],需将按其关键字升序排列。假设前面(nJ)(n>=2)个元素已经是排好顺序的，现在要把第n个元索插到前面的有序元素中，使得这n个元素也是有序的，如此反复，直到数据有序。其中查找插入位置时采用二分查找。b.算

8、法实现vo