排序算法总结

1、飞鱼科技排序算法总结思想&代码实现付英奇2016-2-24In-place sort (不占用额外内存或占用常数内存)：插入排序、选择排序、冒泡排序、堆排序、快速排序。Out-place sort：归并排序、基数排序、桶排序。Stable sort：插入排序、冒泡排序、归并排序、基数排序、桶排序。Unstable sort：选择排序、快速排序、堆排序。时间复杂度为O(N*logN)的算法：归并排序、快速排序、堆排序、希尔排序。时间复杂度为O(N*N)的算法：冒泡排序，选择排序、插入排序时间复杂度为O(N)的算法【桶排序思想】：基数排序，计数排序。空间复杂度O(1)的算法：插入排序、选择

2、排序、冒泡排序、堆排序、希尔排序。空间复杂度O(logN)O(N)的算法：快速排序。空间复杂度O(N)的算法：归并排序空间复杂度O(M)的算法：基数排序、计数排序。void insertionSort(int nums, int length) int i, j, temp; for(i = 1;i < length; +i) j = i - 1; temp = numsi; while(j >= 0 && temp < numsj) /两个条件的顺序不能互换，否则数组越界 numsj+1 = numsj; -j; numsj+1 = temp; /插入数的位

3、置 插入排序：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。桶排序：工作的原理是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。void buctekSort(int nums, int length)int buc100 = 0;int i, k;for(i = 0;i < length; +i)bucnumsi+;for(i = 0;i < 100; +i)if(buci != 0)for(k = buci; k > 0; -k)cout<&l

4、t; i <<'t'void shellSort(int nums,int length)int group, i, j, temp;for(group = length/2; group > 0; group /= 2) /增量的取值规则为第一次取总长度的一半for(i = group; i < length; +i) /第二次取一半的一半,依次累推直到1为止for(j = i - group; j >= 0; j -= group)if(numsj > numsj + group)temp = numsj;numsj = numsj +

5、group;numsj + group = temp;希尔排序：插入排序的改良版。选择排序：每一趟从待排序的记录中选择出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。常用的选择排序有简单选择排序和堆排序。void simple_selection_sort(int nums, int length)/简单选择排序int i,j,temp;for ( i = 0; i < length - 1; i+)int lowIndex = i;for ( j = i + 1; j < length; j+)if (numsj < numslowIndex)lo

6、wIndex = j;swap(numslowindex, numsi);void myswap(int* a, int* b)int temp = *a;*a = *b;*b = temp;void HeapAdjust(int nums, int i, int size)int temp = numsi;int leftChild = 2*i + 1;int rightChild = leftChild + 1;while(leftChild < size)/ 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点if(rightChild < size &

7、;& numsrightChild > numsleftChild)leftChild+;/ 如果父结点的值已经大于孩子结点的值，则直接结束if(numsleftChild <= temp)break;/ 把孩子结点的值赋给父结点numsi = numsleftChild;/ 选取孩子结点的左孩子结点,继续向下筛选i = leftChild;leftChild = 2*i + 1;rightChild = leftChild + 1;numsi = temp;void HeapSort(int nums, int size)InitHeap(nums, size);for(

8、int i = size -1; i > 0; i-)myswap(&numsi, &nums0);HeapAdjust(nums, 0, i);堆排序：void InitHeap(int nums, int size)for(int i = size/2 - 1; i >= 0; i-)HeapAdjust(nums, i, size);void bubbleSort(int nums,int length)int i, k, temp, iExchanged;for(i = 0; i < length - 1; +i)iExchanged = 0; /iE

9、xchanged = 0标志位没有换过for(k = 1; k < length - i; +k) if(numsk-1 > numsk)iExchanged = 1; /iExchanged = 1标志位换过temp = numsk;numsk = numsk-1;numsk-1 = temp;if(!iExchanged) /一次都没有交换，就是有序的，直接退出return;冒泡排序：原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换,直到倒数第二位时结束。int Adjust

10、Array(int nums, int left, int right)int base = numsleft;while(left < right)while(left < right && numsright >= base)right-;if(left < right)numsleft = numsright;left+;while(left < right && numsleft =< base)left+;if(left < right)numsright = numsleft;right-;numsleft

11、= base;return left;快速排序：时间复杂度O(N*logN)最坏O(N2)空间复杂度：O(N*logN)void QuickSort(int nums, int left, int right)if(left < right)int pivot = AdjustArray(nums, left, right);QuickSort(nums,left, pivot-1);QuickSort(nums,pivot+1, right);基数排序：数组实现void RadixSort(int nums, int length)int *radixArraysRADIX_10;fo

12、r(int i = 0; i < 10; i+)radixArraysi = (int*)malloc(sizeof(int) * (length + 1);radixArraysi0 = 0;/index为0处记录这组数据的个数for(int pos = 1; pos <= KEYNUM_31; pos+)/从个位开始到31位int i, j;for(i = 0; i < length; i+)/分配过程int num = GetNumInPos(numsi, pos);int index = +radixArraysnum0;radixArraysnumindex = numsi;for(i = 0, j = 0; i < RADIX_10; i+)/收集for(int k = 1; k <= radixArraysi0; k+)numsj+ = radixArraysik;radixArra