数据结构排序算法

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

2、2. 常见内部排序2.1 交换排序交换排序的基本思想是两两比较待排序记录的关键字，若发生与排序要求相逆，则交换之，反复进行，直到数据有序。交换排序的主要方法有：冒泡排序和快速排序。1). 冒泡排序a. 算法思想已知一组无序数据元素Pn，需将按其关键字升序排列。第一趟对n个元素冒泡得到一个关键字最大的元素Pn-1，第二趟冒泡对n-1个元素得到一个关键字最大的元素Pn-2，依次类推，直到数据有序。b. 算法实现void buble(int arr, int n)bool flag;/用于判断是否发生了交换int i;int temp;/临时变量/反复多轮，从小到大排序。do /一轮排序flag =

3、 false;/反复比较所有相邻的元素，循环比较n-1次。for(i = 1; i < n; i+) /如果顺序不当，就交换他们。if(arri < arri - 1) temp = arri;arri = arri - 1;arri - 1 = temp;/记录本轮已发生交换flag = true;n-;while(flag);/知道本轮没有发生交换，循环退出。注：冒泡排序算法是稳定的，时间复杂度是O(n2)。冒泡排序算法适合只有少量乱序的数据。 2). 快速排序a. 算法思想已知一组无序数据元素Pn，需将按其关键字升序排列。首先任取一个元素Px(通常选取首元素)作为基准，多次比

4、较Px与其它元素并交换。直到当Px可以排在序列的第k位，并且使P0Pk中的每一个元素小于Px，Pk+1Pn-1中的每一个元素不小于Px时，交换Px和Pk。再分别对P0Pk-1和Pk+1Pn-1两组数据元素重复上述过程，直到数据有序。b. 算法实现/交换函数void swap(int *a, int *b)int temp;temp = *a;*a = *b;*b = temp;/快速排序void qsort(int arr, int n)int temp;int *L, *R;if(n <= 1) return;if( n = 2) if(arr1 < arr0) swap(&am

5、p;arr1, &arr0);return;swap(&arr0, &arrn / 2);temp = arr0;L = arr + 1;R = arr + n -1;while(L < R) while(L < R && *L < temp) L+;while(R > arr && *R >= temp) R-;if(L < R) swap(L, R);swap(arr, R);qsort(arr, R - arr);qsort(R + 1, n -(R - arr) - 1);注：快速排序是不稳定的

6、，时间复杂度是O(nlgn)。2.2 插入排序插入排序的基本思想是每次将一个待排序的元素按其关键字的大小，插到前面的有序元素中，反复进行，直到数据有序。插入排序方法主要有：直接插入排序、折半插入排序和希尔排序。1). 直接插入排序a. 算法思想已知一组无序数据元素Pn，需将按其关键字升序排列。假设前面(n-1) (n>=2)个元素已经是排好顺序的，现在要把第n个元素插到前面的有序元素中，使得这n个元素也是有序的，如此反复，直到数据有序。其中查找插入位置时采用顺序查找。b. 算法实现void insert(int arr, int n)int i, j;int temp;for(i = 1

7、; i < n; i+) /从小到大排序，反复n-1次。if(arri >= arri -1) continue;temp = arri;/另存一份for(j = i; j > 0 && arrj - 1 > temp; j-) arrj = arrj - 1;arrj = temp;/插入备份注：直接插入排序算法是稳定的，时间复杂度是O(n2)。2). 折半插入排序a. 算法思想已知一组无序数据元素Pn，需将按其关键字升序排列。假设前面(n-1) (n>=2)个元素已经是排好顺序的，现在要把第n个元素插到前面的有序元素中，使得这n个元素也是有序的

8、，如此反复，直到数据有序。其中查找插入位置时采用二分查找。b. 算法实现void binaryInsert(int arr, int n)int i, j, low, mid, high;int temp;for(i = 1; i < n; +i) /从小到大排序，反复n-1次。temp = arri;/另存一份low = 0;high = i - 1;while(low <= high) /二分查找待插入位置(high+1)mid = (low + high) / 2;if(arri < arrmid) high = mid - 1;else low = mid + 1;f

9、or(j = i - 1; j >= high + 1; -j) arrj + 1 = arrj;/后移元素，留出插入空位。arrhigh + 1 = temp;/插入备份注：折半插入排序算法是稳定的，时间复杂度是O(n2)。3). 希尔排序a. 算法思想已知一组无序数据元素Pn，需将按其关键字升序排列。先将要排序的一组元素按某个增量d分成若干组，每组中元素的下标相差d。对每组中全部元素进行排序。然后再用一个较小的增量对它进行分组，在每组中再进行排序，直到增量减小到1时，整个要排序的数被分在一组，排序完成，数据有序。b. 算法实现void shellSort(int array, int

10、 n)int i, j, d;int temp, flag;d = n;/外循环控制增量(分组)，直到d为1时止。do d = d / 2;/中间循环是在某一个分组值下，分别对各组进行组内排序，若发生了元素交换，继续循环，直到各组内无元素交换为止。do flag = 0;/内循环是从第一个元素开始，按某个d值的间距进行组内比较，若有逆序，则进行交换。for(i = 0; i < n - d; +i) j = i + d;if(arrayi > arrayj) temp = arrayi;arrayi = arrayj;arrayj = temp;flag = 1;while(fla

11、g);while(d > 1);注： 希尔排序是不稳定的，时间复杂度是O(n1.3)。同时希尔排序的时间复杂度依赖于所取增量序列，一般认为是O(nlgn)。2.3 选择排序选择排序的基本思想是每次从待排序的元素中选出关键字最小的元素，顺序存放在有序序列的后面，反复进行，直到数据有序。选择排序方法主要有：直接选择排序和堆排序。1). 直接选择排序a. 算法思想已知一组无序数据元素Pn，需将按其关键字升序排列。第一趟，从n个元素中选出关键字最小的一个元素与第一个位置的元素交换。第二趟，从剩下的元素中再选择关键字最小的元素与第二个位置的元素交换。第三趟，如此反复，直到数据有序。 b. 算法实现

12、void select(int arr, int n)int i, j;int min;/最小元素下标for(i = 0; i < n - 1; i+) min = i;/将第一个元素作为最小元素for(j = i + 1; j < n; j+) /反复查找其后n-1个更小的元素if(arrj < arrmin) /发现更小的，则记录其下标。min = j;if(i != min) /防止相同位置的交换。int temp;temp = arri;arri = arrmin;arrmin = temp;注：选择排序是不稳定的，时间复杂度是O(n2)。2). 堆排序堆排序是一种树

13、形选择排序，是对直接选择排序的有效改进。a.堆的定义如下：具有n个元素的序列(h1, h2, ., hn)，当且仅当满足(hi>=h2i, hi>=2i+1)或(hi<=h2i, hi<=2i+1) (i=1, 2, ., n/2)时称之为堆。注：若将此序列Pn看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树，树中任一非叶结点的关键字均不大于(或不小于)其左右孩子结点的关键字。a. 算法思想已知一组无序数据元素Pn，需将按其关键字升序排列。初始时把Pn看作是以P0为树根，P1.2.3.n-1依次从左向右逐层排列的一棵顺序存储的完全二叉树，调整它们的存

14、储顺序， 使之成为一个堆。然后将根节点与堆的最后一个节点交换，再对前面n-1个元素重新调整使之成为堆，并将根节点与新堆的最后一个节点交换，依此类推，直到数据有序。b. 算法实现/建堆/调整成大根堆/array是待调整数组，length是数组的长度，i是待调整元素的位置(下标)。void heapAdjust(int array, int length, int i)int temp;/保存开始待调整的元素int child;for(temp = arrayi; 2 * i + 1 < length; i = child) /2*i+1为待调整元素左子树的位置，若默认下标从1开始，则为右子

15、树位置。/保存左子节点的位置child = 2 * i + 1;/获取子节点中较大的节点位置，要么左子树位置，要么右子树位置。if(child < length -1 && arraychild < arraychild + 1) +child;/判断较大的子节点是否大于父节点，若是，把较大的子节点向上移动，替换其父节点。不用担心，父节点之前已经另存了一份。if(arraychild > temp) arrayi = arraychild;arraychild = temp;else break;arrayi = temp;/最后把开始元素放到合适的位置上/堆

16、排序void heapSort(int array, int length)int i;/创建堆/若默认第一个节点的下标为0，操作从length/2-1位置开始。/若默认第一个节点的下标为1，操作从length/2位置开始。for(i = length / 2 - 1; i >= 0; -i) heapAdjust(array, length, i);/调整堆/从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素。for(i = length - 1; i > 0; -i) /把第一个元素和当前的最后一个元素交换，保证当前的最后一个位置的元素都是在现在的这个序列之中

17、最大的。 int temp;temp = array0;array0 = arrayi;arrayi = temp;/重新从下标为0的位置开始调整成堆，不断缩小调整的范围，每一次调整完毕保证第一个元素是当前序列的最大值。heapAdjust(array, i , 0);/对根结点重新调整使之成为大根堆注：堆排序是不稳定的，时间复杂度是O(nlgn)。2.4 归并排序归并排序的基本思想是把待排序序列分为若干个子序列，每个子序列是有序的，然后再把有序子序列合并为整体有序序列。若将两个有序表合并成一个有序表，称为二路归并。a. 二路归并算法思想定义两个数组temp1m, temp2n，分别将待合并数

18、组mergeend-start+1的两部分元素拷贝到定义的数组中，并设置相应的监视哨。合并时，依次比较temp1i和temp2j的大小，并将较小的元素拷贝到mergek中，然后让相应元素的下标加1，依此类推，直到合并成功。b. 算法实现/合并void Merge(int array, int start, int mid, int end) int temp110, temp210; int n1, n2;int i, j, k; n1 = mid - start + 1; n2 = end - mid; for (int i = 0; i < n1; +i) /拷贝前半部分元素 tem

19、p1i = arraystart + i; for (int i = 0; i < n2; i+) /拷贝后半部分元素 temp2i = arraymid + i + 1; temp1n1 = temp2n2 = 5211314;/拷贝完成后，分别将后一个下标对应的元素设置为足够大。好处是两部分数组元素将完全合并，无剩余。 for (k = start, i = 0, j = 0; k <= end; k+) /逐个判断两部分数组中元素的大小次序，然后放到相应的位置。 if (temp1i <= temp2j) arrayk = temp1i; i+; else arrayk

20、 = temp2j; j+; /划分void MergeSort(int array, int start, int end) if(start < end) int mid; mid = (end + start) / 2; MergeSort(array, start, mid);/ 对前半部分进行划分MergeSort(array, mid + 1, end);/对后半部分进行划分Merge(array, start, mid, end);/合并前后两部分 注：归并排序是稳定的，时间复杂度是O(nlgn)。2.5 基数排序基数排序的基本思想是将所有待排元素(必须是正整数)统一认为是

21、数位相同的数，数位较短的在最左边补零。然后从最边位(最左边或最右边)开始， 依次进行一次稳定排序，这样从一边一直到另一边的排序完成之后， 数据有序。a. 算法思想基数排序是一种分配排序，排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。从最低位关键字起，按照关键字位值的不同将序列中的元素"分配"到"基"个队列中，然后再"收集"之，如此重复d次即可。其中：d为位值的个数，位值的取值范围的长度(又称基)为radix。/数字范围：0-9，基为：10b. 算法实现#define BITNUM 6/位值个数#define RAD

22、IX 10/基值#define MAX_SPACE 50/最大可用空间/静态链表结点类型定义typedef struct BitNode int data;/数据域int bitsBITNUM;/数据位值域int next;/指针域bitnode;/静态链表类型定义typedef struct StaticLinkList bitnode rMAX_SPACE;/待排序序列，r0为头结点，头结点的数据域用于存放其它信息。int length;/当前长度int bitnum;/位置个数linklist;/定义数组类型，用于分别指向基值个队列。typedef int arraytypeRADIX;

23、/分配/建立RADIX个队列，使同一队列中元素的bitsi相同。/front0.RADIX-1和rear0.RADIX-1分别指向各队列中第一个和最后一个元素。void distribute(bitnode R, int i, arraytype front, arraytype rear)int j, p;for(j = 0; j < RADIX; +j) /各队列初始化为空frontj = rearj = 0;for(p = R0.next; p; p = Rp.next) j = Rp.bitsi;/映射i位值if(!frontj) frontj = p;/若frontj为空，则把p位置对应的元素链接到frontj的头指针上。else Rrearj.next = p;/若frontj的头指针上已经链接了，这时让上一个以j为位值的元素的next指向当前元素。rearj = p;/尾指针指向新的元素下标/收集/本算法按bitsi值从小到大地将front0.RADIX-1所指各队列依次链接成为一个静态链表void collect(bitno