算法大总结之 |
您所在的位置：网站首页 › 从小到大用英语翻译 › 算法大总结之 |
|
目录
1. 冒泡排序1.1. 算法讲解1.2. 代码实现
2. 选择排序2.1. 算法讲解2.2. 代码实现
3 插入排序2.1. 算法讲解2.2. 代码实现
4 希尔排序2.1. 算法讲解2.2. 代码实现
5 归并排序2.1. 算法讲解2.2. 代码实现
6 快速排序6.1. 算法讲解6.2. 代码实现
7 堆排序2.1. 算法讲解2.2. 代码实现
8 计数排序2.1. 算法讲解2.2. 代码实现
9 桶排序2.1. 算法讲解2.2. 代码实现
10 基数排序2.1. 算法讲解2.2. 代码实现
附录1. 10大经典排序算法性能分析2. C/C++的内置排序函数2.1. c++的`sort`函数2.1.1. 函数简述2.1.2. `cmp`叙述2.1.3. 代码实现
2.2 c语言的`qsort`函数2.1.1. 函数简述2.1.2. `cmp`叙述2.1.3. 代码实现
1. 冒泡排序
冒泡排序，顾名思义，就是出头的被排序。其算法复杂度为O( n 2 n^{2} n2)，空间复杂度为O( 1 1 1)。 1.1. 算法讲解 将第j个元素和后面的元素依次对比，如果大于序列为j+1的元素，就进行交换。作为对比的基础元素j取值范围为"0 => size - 2"。因为j + 1不可超过size - 1。因而，需要进行对比的j有size - 1个，这个组别用字母i表示。当排序到第i组元素时候，需要做对比的就只需size - i - 1个。以第一次对比为例子，从第一个到最后一个元素都和相邻的两两对比交换，因此这组所有数中最大的已经交换到了最后一位。所以下一次，就不需要考虑它了。第二次，这一组最大的交换到了倒数第二位…。因此需要做对比的就只需size - i - 1个。 1.2. 代码实现 void BubbleSort(int a[], int size) { for (int i = 0; i int temp = 0; if (a[j] > a[j + 1]) { temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } } } 2. 选择排序选择排序也是非常直观的，唯一的好处可能就是不占用额外的内存空间。算法复杂度为O( n 2 n^{2} n2)，空间复杂度为O( 1 1 1)。 2.1. 算法讲解 选择排序认为前i个元素是排序好的，因此将后面的元素排序即可。i的取值范围为0 => size - 1。对排序第i个元素的那一组，将i的下标暂存(MIN)，并认为这个元素是最小的(a[MIN])。如果后面的元素有比次元素小得，将**a[MIN]**更新为更小的元素，并将所记录的最小元素下标(MIN)也更新。在这一组遍历结束，如果MIN不是初始值0了，意味着这一组的第一个元素不是最小的，那么将这个最小的元素和第一个元素做交换，以保证从开头到这个元素的这一段是已经排序好的。将第2步，第3步重复进行直至所有。 2.2. 代码实现 void SelectSort(int a[], int size) { int MIN = 0; for (int i = 0; i if (a[j] int temp = 0; temp = a[i]; a[i] = a[MIN]; a[MIN] = temp; } } } 3 插入排序插入排序就好像打扑克牌整理牌组一样，从后面看起，如果此牌小于前面整理好的牌，就插入前面，因而前面整理好的牌，在被插入的后面的，依次后移一位。 可以说插入排序是远离最直观的，算法复杂度为O( n 2 n^{2} n2) ，空间复杂度为O( 1 1 1)。 2.1. 算法讲解 排序分为若干组进行，其中的一组为从第i个元素开始，直到最后一个元素为止。由于每进行一次排序，前面的都已经排序完成，因此只需对比这第i个元素是不是比前面i-1个元素小就行。若第i个元素小于前面i-1个元素中的第j个元素，就首先将这第i个元素记录下来，然后把从第j个元素到第i-1个元素依次后移，最后再把记录下来的元素，插入第j个位置。将此步骤进行循环即可。 2.2. 代码实现 void InsertSort(int a[], int size) { int i, j, temp; for (i = 1; i temp = a[i]; for (j = i - 1; j >= 0 && a[j] > temp; j--) { a[j + 1] = a[j]; } a[j + 1] = temp; } } } 4 希尔排序 2.1. 算法讲解 2.2. 代码实现 void ShellSort(int a[], int size) { for (int gap = size / 2; gap > 0; gap /= 2) { for (int i = gap; i a[j + gap] = a[j]; } if (j != 0) a[j + gap] = temp; } } } 5 归并排序归并排序是要将元素先分组，分到两两一组，然后再合并，合并时候，按大小合并。其算法复杂度为O( n l o g 2 n nlog_2n nlog2n)，空间复杂度为O( n n n)。 2.1. 算法讲解 2.2. 代码实现 void MergeSort(int a[], int left, int right) { if (left >= right) return; int Len = right - left + 1; int mid = (right + left) / 2; int start1 = left; int end1 = mid; int start2 = mid + 1; int end2 = right; MergeSort(a, start1, end1); MergeSort(a, start2, end2); int i = 0; int *temp = (int *)malloc(Len * sizeof(int)); while (start1 int temp = *a; *a = *b; *b = temp; } int QuickPartition(int a[], int low, int high) { int pivot = a[high]; int i = low; for (int j = low; j swap(&a[i], &a[j]); i++; } } swap(&a[i], &a[high]); return i; } void QuickSort(int a[], int low, int high) { if (low 0,2,87,39,49,34,62,53,6,44,98}; #define LeftChild(i) (2 * (i) + 1) void Swap(int* a,int* b) { int temp=*a; *a=*b; *b=temp; } void PercDown(int A[], int i, int N) { int child; ElementType Tmp; for (Tmp = A[i]; 2*i+1 int i; for (i = N / 2; i >= 0; --i) PercDown(A, i, N); //构造堆 for(i=N-1;i>0;--i) { Swap(&A[0],&A[i]); //将最大元素（根）与数组末尾元素交换，从而删除最大元素，重新构造堆 PercDown(A, 0, i); } } void Print(int A[],int N) { int i; for(i=0;i int arr[10]={2,87,39,49,34,62,53,6,44,98}; Print(arr,10); printf("\n"); HeapSort(arr,10); Print(arr,10); printf("\n"); return 0; } 8 计数排序 2.1. 算法讲解 2.2. 代码实现 void CountSort(int a[], int size) { int MAX = 0; for (int i = 0; i MAX ? a[i] : MAX; MAX++; //容器的数量为最大元素值+1(因为从0开始) int *sort = (int *)malloc(size * sizeof(int)); //排序好的数组 int *container = (int *)malloc(MAX * sizeof(int)); //容器 memset(sort, 0, size * sizeof(int)); memset(container, 0, size * sizeof(int)); for (int j = 0; j return a > b; }结构体排序: typedef struct _stu { int age; string name; }stu; bool cmp(stu a, stu b) { return a.age return a.age srand(i); //随机数种子 student[i].age = rand() % 20; //生成不大于20的随机数 student[i].name = "LiLei"; } for (int i = 0; i cout int age; char name[10]; }stu; int cmp(const void* a, const void* b) { stu* A = (stu*)a; stu* B = (stu*)b; return A->age - B->age; }C语言中的cmp是将指针转为void指针的。 2.1.3. 代码实现对结构体的排序做一次代码示例 #include #include #include typedef struct _stu { int age; char name[10]; }stu; int cmp(const void* a, const void* b) { stu* A = (stu*)a; stu* B = (stu*)b; return A->age - B->age; } int main() { stu student[10]; for (int i = 0; i printf("The %dth student age=%d, name=%s\n", i, student[i].age, student[i].name); } qsort(student, 10, sizeof(stu), cmp); //注意这里和sort的区别 printf("*********************************\n"); for (int i = 0; i |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |