末尾 技术分享 下标 ima http 直接 wap temp 部分
一.冒泡排序(Bubble Sort)
基本思想:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。
- //冒泡排序
- void BubbleSort(int *p, int length)
- {
- for (int i = 0; i < length-1; i++)
- {
- for (int j =length-1; j>=i;j--)
- {
- if (p[j-1] > p[j])
- {
- swap(p[j-1], p[j]);
- }
- }
- }
- }
排序前的顺序为:9 1 5 8 3 7 4 6 2
当i=1时,交换的情况如下:
二.简单选择排序(Simple Selection Sort)
通过n-1次关键字间的比较,从n-i+1个记录中选择最小的记录,并和第i次(1≤i≤n)记录交换。
- //简单选择排序
- void SimSelSort(int *p, int length)
- {
- int i, j, min;
- for (i = 0; i < length - 1; i++)
- {
- min = i; //记录最小值的下标,初始化为i
- for (j=i+1;j<=length-1;j++)
- {
- if (p[j] < p[min])
- min = j; //通过不断地比较,得到最小值的下标
- }
- swap(p[i], p[min]);
- }
- }
三.直接插入排序
把一个记录直接插入到已经排好序的有序表中,从而得到一个新的,记录数增1的有序表。
- //直接插入排序
- void StrInserSort(int *p, int length)
- {
- int i, j;
- for (i =1; i <length; i++)
- {
- if ( p[i]<p[i-1])
- {
- int tmp;
- tmp = p[i];
- for (j = i - 1; p[j] > tmp; j--)
- p[j+1] = p[j];
- p[j+1] = tmp;
- }
- }
- }
四.希尔排序(Shell Sort)
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
- void ShellSort(int *p, int length)
- {
- int i, j;
- int increment = length;
- do {
- increment = increment / 3 +1;
- for (i = increment ; i <= length - 1; i++)
- {
- if (p[i] < p[i - increment])
- {
- int tmp;
- tmp = p[i];
- for (j = i - increment; j >= 0 && tmp < p[j]; j -= increment)
- p[j + increment] = p[j];
- p[j + increment] = tmp;
- }
- }
- } while (increment > 1);
- }
五.堆排序(Heap Sort)
1.堆的定义
堆是具有下列性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。
2.堆排序
堆排序的基本思想(利用堆,如大顶堆进行排序):将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根结点。将它移走(其实就是将它与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余n-1个序列重新构造成一个堆,这样就会得到n个元素的次小值。如此反复执行,便能得到一个有序序列。
主要问题:
1.如何由一个无序序列构建成一个堆?
2.如何在输出堆顶元素后,调整剩余元素成为一个新的堆?
- //构造最大堆
- void MaxHeapFixDown(int *p, int i, int length) {
- int j = 2 * i + 1;
- int temp = p[i];
- while (j<length) {
- if (j + 1<length && p[j]<p[j + 1])
- ++j;
- if (temp>p[j])
- break;
- else {
- p[i] = p[j];
- i = j;
- j = 2 * i + 1;
- }
- }
- p[i] = temp;
- }
- //堆排序
- void HeapSort(int *p, int length) {
- for (int i = length / 2 - 1; i >= 0; i--)
- {
- MaxHeapFixDown(p, i, length);
- }
- for (int i = length - 1; i >= 1; i--)
- {
- swap(p[i], p[0]);
- MaxHeapFixDown(p, 0, i);
- cout << "i的值:" << i << " 排序:";
- ergodic(p, 9);
- }
- }
六.归并排序(Merging Sort)
归并排序就是利用归并思想实现的排序方法。原理:假设初始序列含有n个记录,则可以看成是n个有序的子序列,每个子序列长度为1,然后再两两归并,得到[n/2]个长度为2或1的有序子序列;再两两归并….,如此重复,直到的一个长度为n的有序序列为止,称为2路归并排序。
七.快速排序(Quick Sort)
快速排序的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另外一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。
- //快速排序
- void QuickSort(int *p, int l, int r)
- {
- if (l< r)
- {
- int i = l, j = r, x = p[l];
- while (i < j)
- {
- while (i < j && p[j] >= x) // 从右向左找第一个小于x的数
- j--;
- if (i < j)
- p[i++] = p[j];
- while (i < j && p[i]< x) // 从左向右找第一个大于等于x的数
- i++;
- if (i < j)
- p[j--] = p[i];
- }
- p[i] = x;
- QuickSort(p, l, i - 1); // 递归调用
- QuickSort(p, i + 1, r);
- }
- }
总结
参考:《大话数据结构》
[数据结构(二)]七种排序算法的C++简单实现
末尾 技术分享 下标 ima http 直接 wap temp 部分
原文:http://www.cnblogs.com/youngsea/p/7798451.html
来源: http://www.bubuko.com/infodetail-2384115.html