排序的相关概念 排序的分类
1.内排序内排序是在排序整个过程中,带排序的所有记录全部放置在内存中。 影响内排序的主要因素
内排序的分类根据排序过程中借助的主要操作,内排序分为:
2.外排序外排序是由于排序的记录个数太多,不能同时放置在内存中,整个排序过程需要在内外存之间多次交换数据才能进行。 按照算法的复杂度分类
一、冒泡排序算法因为在冒泡排序中要用到顺序表结构和数组两元素的交换,先把这些写成函数 #include <stdio.h> #include <stdlib.h>
#define MAXSIZE 100 #define TRUE 1 #define FALSE 0
typedef struct { int r[MAXSIZE + 1]; int length; }SqList;
void swap(SqList *L, int i, int j){ int temp = L->r[i]; L->r[i] = L->r[j]; L->r[j] = temp; } 1.1 冒泡排序的初级版实现冒泡排序(Bubble Sort)是一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。
对于这段代码,是最简单的冒泡,其实就是最简单的交换排序而已。它的思路就是让每一个关键字,都和它后面的每一个关键字比较,如果大则交换,这样第一位置的关键字在第一次循环后一定变成最小值。 假设我们待排序的关键字序列是
1.2 冒泡排序的实现对于上面的算法,代码虽然简单易懂,但是效率非常低。可以改进成接下来的代码 void BubbleSort(SqList *L){ int i,j; for (i = 1; i < L->length; i++) for (j = L->length - 1; j >= i; j--) if (L->r[j] > L->r[j+1]) swap(L, j, j+1); } 代码解释假设我们待排序的关键字序列是
1.3 冒泡排序的优化
测试#define N 9 int main(int argc, const char * argv[]) { int i; int d[N] = {9,1,5,8,3,7,4,6,2}; SqList l0; for (i = 0; i < N; i++) l0.r[i+1] = d[i]; l0.length = N; printf('排序前:\n'); for (i = 0; i < l0.length; i++) { printf('%d ', l0.r[i+1]); } printf('\n');
printf('1.0 初级冒泡排序结果:\n'); BubblSort0(&l0); for (i = 0; i < l0.length; i++) { printf('%d ', l0.r[i+1]); } printf('\n'); printf('1.1 冒泡排序结果:\n'); BubbleSort(&l0); for (i = 0; i < l0.length; i++) { printf('%d ', l0.r[i+1]); } printf('\n');
printf('1.2 优化后冒泡排序结果:\n'); BubbleSort1(&l0); for (i = 0; i < l0.length; i++) { printf('%d ', l0.r[i+1]); } printf('\n');
return 0; } 测试结果 二、简单选择排序简单选择排序法(Simple Selection Sort)是通过 简单选择排序法的工作原理是:每一次从无序组的数据元素中选出最小(或最大)的一个元素,存放在无序组的起始位置,无序组元素减少,有序组元素增加,直到全部待排序的数据元素排完。
代码说明
三、直接插入排序直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录增1的有序表。 直接插入排序的核心思想:将一个记录插入到一个已经排序好的表中,以得到一个记录增加1的有序表。并且它把当前元素大的记录都往后移动,用以腾出“自己”该插入的位置。当n-1趟插入完成后该记录就是有序序列。
代码说明
四、希尔排序希尔排序是对直接插入排序的改进:
希尔排序的核心思想:希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止 void ShellSort(SqList *L){ int i,j; int increment = L->length; do { increment = increment /3 +1; for (i = increment + 1; i < L->length; i++) { if (L->r[i] < L->r[i-increment]) { L->r[0] = L->r[i]; for (j = i - increment; i >0 && L->r[0] < L->r[j]; j -= increment) L->r[j+increment] = L->r[j]; L->r[j+increment] = L->r[0]; } } } while (increment > 1); } 代码说明
五、堆排序堆的概念堆是具有如下性质的完全二叉树:
堆排序算法堆排序(Heap Sort)是利用堆(假设是大顶堆)进行排序。
堆排序算法核心
堆排序算法代码实现
堆排序算法代码说明
六、归并排序归并排序(Merging Sort)是利用归并的思想实现的。2路归并排序的核心思想如下:
6.1归并排序的实现思路(递归实现)
归并排序的代码实现(递归实现)#pragma - 6.归并排序(递归实现)
void Merge(int SR[], int TR[], int i, int m, int n){ int j, k, l; for (j = m+1, k = i; i <= m && j <= n; k++) { if (SR[i] < SR[j]) TR[k] = SR[i++]; else TR[k] = SR[j++]; } if (i <= m) { for (l=0; l <= m-i; l++) TR[k+l] = SR[i+l]; } if (j <= n) { for (l=0; l <= n-j; l++) TR[k+l] = SR[j+l]; } }
void MSort(int SR[], int TR1[], int s, int t){
int m; int TR2[MAXSIZE+1]; if (s == t) { TR1[s] = SR[s]; }else{ m = (s+t)/2; MSort(SR, TR2, s, m); MSort(SR, TR2, m+1, t); Merge(TR2, TR1, s, m, t); } }
void MergeSort(SqList *L){ MSort(L->r, L->r, 1, L->length); } 归并排序的总结(递归实现)
6.2归并排序的实现(迭代非递归实现)用迭代实现的话,可以从最小的序列开始归并直到完成。
归并的迭代实现总结
七、快速排序快速排序(Quick Sort)的基本思想是:
快速排序的实现思路
快速排序的代码实现#pragma - 8.快速排序
int Partition(SqList * L, int low, int high){ int pivotkey; pivotkey = L->r[low]; while (low < high) { while (low < high && L->r[high] >= pivotkey) high --; swap(L, low, high); while (low < high && L->r[low] <= pivotkey) high++; swap(L, low, high); } return low; }
void QSort(SqList *L, int low, int high){ int pivot; if (low < high) { pivot = Partition(L, low, high); QSort(L, low, pivot-1); QSort(L, pivot+1, high); } }
void QuickSort(SqList *L){ QSort(L, 1, L->length); } 快速排序的代码说明
快速排序的优化
三数取中(median-of-three)法代码:
快速排序优化后的代码int Partition1(SqList * L, int low, int high){ int pivotkey; int m = low + (high - low)/2; if (L->r[low] > L->r[high]) swap(L, low, high); if (L->r[m] > L->r[high]) swap(L, high, m); if (L->r[m] > L->r[low]) swap(L, m, low); pivotkey = L->r[low]; L->r[0] = pivotkey; while (low < high) { while (low < high && L->r[high] >= pivotkey) high--; L->r[low] = L->r[high]; while (low < high && L->r[low] <= pivotkey) low++; L->r[high] = L->r[low]; } L->r[low] = L->r[0]; return low; }
void QSort1(SqList *L, int low, int high){ int pivot; if ((high -low) > MAX_LINEGIH_INSERT_SORT) { while (low < high) { pivot = Partition1(L, low, high); QSort1(L, low, pivot-1);
low = pivot+1; } }else InsertSort(L); }
void QuickSort1(SqList *L){ QSort1(L, 1, L->length); }
作者:STzen |
|