算法收集
插入排序
思想:遍历到第N个元素的时候前面的N-1个元素已经是排序好的了,那么就查找前面的N-1个元素把这第N个元素放在合适的位置,如此下去直到遍历完序列的元素为止.算法的复杂度也是简单的,排序第一个需要1的复杂度,排序第二个需要2的复杂度,因此整个的复杂度就是1 + 2 + 3 + … + N = O(N ^ 2)的复杂度
void InsertSort(int array[], int length) { int i, j, key; for (i = 1; i < length; i++) { key = array[i]; for (j = i - 1; j >= 0 && array[j] > key; j--) { array[j + 1] = array[j]; } array[j + 1] = key; } }
shell排序
思想:对插入排序的一个改装,它每次排序把序列的元素按照某个增量分成几个子序列,对这几个子序列进行插入排序,然后不断的缩小增量扩大每个子序列的元素数量,直到增量为一的时候子序列就和原先的待排列序列一样了,此时只需要做少量的比较和移动就可以完成对序列的排序了.
void ShellSort(int array[], int length) { int temp; for (int increment = length / 2; increment > 0; increment /= 2) { for (int i = increment; i < length; ++i) { temp = array[i]; for (int j = i; j >= increment; j -= increment) { if (temp < array[j - increment]) { array[j] = array[j - increment]; } else { break; } } array[j] = temp; } } }
冒泡排序
思想:每次遍历完序列都把最大(小)的元素放在最前面,然后再对剩下的序列从父前面的一个过程,每次遍历完之后待排序序列就少一个元素,当待排序序列减小为只有一个元素的时候排序就结束了.因此,复杂度在最坏的情况下是O(N ^ 2).
void Swap( int * a, int * b) { int temp; temp = *a; *a = *b; *b = temp; } void BubbleSort( int array[], int length) { bool exchange; for ( int i = 0 ; i < length; ++ i) { exchange = false ; for ( int j = i + 1 ; j < length; ++ j) { if (array[j] < array[i]) { exchange = true ; Swap( & array[j], & array[i]); } } if( false == exchange) break ; } }
快速排序
思想: 选定一个枢纽元素,对待排序序列进行分割,分割之后的序列一个部分小于枢纽元素,一个部分大于枢纽元素,再对这两个分割好的子序列进行上述的过程.对一个给定范围的子序列选定一个枢纽元素,执行完函数之后返回分割元素所在的位置,在分割元素之前的元素都小于枢纽元素,在它后面的元素都大于这个元素
int Partition(int 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; } void QuickSort(int array[], int low, int high) { if (low < high) { int n = Partition(array, low, high); QuickSort(array, low, n); QuickSort(array, n + 1, high); } }
归并排序
思想:把待排序序列分成相同大小的两个部分,依次对这两部分进行归并排序,完毕之后再按照顺序进行合并.
void Merge(int array[], int start, int mid, int end) { int 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++; } } } void MergeSort(int array[], int start, int end) { if (start < end) { int i; i = (end + start) / 2; MergeSort(array, start, i); MergeSort(array, i + 1, end); Merge(array, start, i, end); } }
堆的定义:n个关键字序列Kl,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):
ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤),若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。堆的这个性质使得可以迅速定位在一个序列之中的最小(大)的元素.
堆排序算法的过程如下:
1)得到当前序列的最小(大)的元素
2)把这个元素和最后一个元素进行交换,这样当前的最小(大)的元素就放在了序列的最后,而原先的最后一个元素放到了序列的最前面
3)的交换可能会破坏堆序列的性质(注意此时的序列是除去已经放在最后面的元素),因此需要对序列进行调整,使之满足于上面堆的性质.重复上面的过程,直到序列调整完毕为止.
//array是待调整的堆数组,i是待调整的数组元素的位置,length是数组的长度 void HeapAdjust(int array[], int i, int nLength) { int nChild, nTemp; for (nTemp = array[i]; 2 * i + 1 < nLength; i = nChild) { nChild = 2 * i + 1; if (nChild != nLength - 1 && array[nChild + 1] > array[nChild]) ++nChild; if (nTemp < array[nChild]) { array[i] = array[nChild]; } else { break; } } array[i] = nTemp; } void HeapSort(int array[], int length) { for (int i = length / 2 - 1; i >= 0; --i) { HeapAdjust(array, i, length); } for (int i = length - 1; i > 0; --i) { Swap(&array[0], &array[i]); HeapAdjust(array, 0, i); } }
建议继续学习:
- 为什么算法这么难? (阅读:10723)
- 15道使用频率极高的基础算法题 (阅读:5580)
- 一些有意思的算法代码 (阅读:3957)
- Fastbit中的bitmap索引算法 (阅读:3756)
- 算法的意义 (阅读:3329)
- 基于漏桶(Leaky bucket)与令牌桶(Token bucket)算法的流量控制 (阅读:3083)
- 研发面试最常用的10大算法 (阅读:2959)
- 生成特定分布随机数的方法 (阅读:2674)
- 机器学习算法之LightGBM (阅读:1542)
- 聚类算法之ISODATA (阅读:1399)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:SpawN 来源: SpawN
- 标签: 算法
- 发布时间:2010-11-01 20:07:17
- [66] Go Reflect 性能
- [65] Oracle MTS模式下 进程地址与会话信
- [64] 如何拿下简短的域名
- [59] android 开发入门
- [59] IOS安全–浅谈关于IOS加固的几种方法
- [58] 图书馆的世界纪录
- [58] 【社会化设计】自我(self)部分――欢迎区
- [53] 视觉调整-设计师 vs. 逻辑
- [47] 界面设计速成
- [46] 读书笔记-壹百度:百度十年千倍的29条法则