|
一、算法概述1 算法分类十种常见排序算法可以分为两大类：
非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。
2 算法复杂度
3 相关概念稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
二、排序算法1. 冒泡排序其大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。这个过程类似于水泡向上升一样，因此而得名。
最好情况：已经是有序的，只需要完成n-1次扫描，不需要互换操作。O(n)。
最坏情况：即逆序，需要n-1次扫描，每次都需要互换操作。需要 (n-1)+(n-2)+…+2+1=n(n-1)/2次。O(n^2)。
#include <stdio.h>
int main()
{
//初始化数组
int a[] = {3,5,1,9,2,6,4,8,7};
int i,j,temp,flag;
//获取数组字段个数
int n = sizeof(a) / sizeof(int);
//升序
for (i = 0; i < n - 1; i++) {
flag = 0;
for (j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j+1]) {
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
flag = 1;
}
}
if (!flag) break;
}
for (i = 0; i < n; i++) {
printf("%d ", a[i]);
}
return 0;
}
2. 快速排序基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的比另一部分记录的都小，分别对这两部分继续进行排序。
快速排序的时间性能取决于快速排序递归的深度，可以用递归树来描述递归算法的执行情况。如下图，它是{50, 10, 90, 30, 70, 40, 80, 60, 20}在快速排序过程中的递归过程，由于第一个关键数字是50，正好是待排序的序列中间值，因此递归树是平衡的，此时性能也比较好。
最好情况：Parition每次都划分均匀，递归树深度 ，每层递归遍历总次数为n，需要nT(1)+nlog(n)。
最坏情况：待排序序列为正序或逆序，每次划分只得到比上一次少一个记录的子序列，另一个为空。如果用递归树画出来，它就是一颗斜树。需要执行n-1次递归调用，第i次需要n-i次关键字比较。因此比较次数n-1+n-2+…+2+1=n(n-1)/2。
平均情况： 。数学归纳法证明，
空间复杂度：主要是递归造成的栈空间的使用，最好情况，递归树的深度为log(n)，其空间复杂度也就是。最坏情况，需要进行n-1次递归调用，空间复杂度为O(n)。平均情况，空间复杂度也为。
#include <stdio.h>
void quickSort(int a[], int left, int right)
{
int i,index,temp;
if (left >= right) {
return;
}
index = left;
for (i = left; i < right; i++) {
if (a[i] <= a[right]) {
if (a[i] != a[index]) {
temp = a[i];
a[i] = a[index];
a[index] = temp;
}
index++;
}
}
if (index != right) {
temp = a[index];
a[index] = a[right];
a[right] = temp;
}
quickSort(a, left, index-1);
quickSort(a, index+1, right);
}
int main()
{
//初始化数组
int a[] = {80,93,60,12,42,30,68,85,10,100};
int i,j,temp,incre,current,min;
//获取数组字段个数
int n = sizeof(a) / sizeof(int);
//升序
//快速排序
int right = n - 1;
quickSort(a, 0, right);
for (i = 0; i < n; i++) {
printf("%d ", a[i]);
}
return 0;
}
3. 插入排序基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。
最好情况：表本身就是有序的，需要比较n-1次，不需要移动。O(n)
最坏情况：待排表是逆序，需要比较2+3+…+n=(n+2)(n-1)/2次，记录的移动次数也达到了3+4+…+(n+1)=(n+4)(n-1)/2次。
平均情况：如果记录随机，平均比较和移动次数约 次，
#include <stdio.h>
int main()
{
//初始化数组
int a[] = {3,5,1,9,2,6,4,8,7};
int i,j,temp,current,f;
//获取数组字段个数
int n = sizeof(a) / sizeof(int);
//升序
for (i = 1; i < n; i++) {
current = i;
j = i - 1;
while (j >= 0 && a[current] < a[j]) {
temp = a[current];
a[current] = a[j];
a[j] = temp;
current = j;
j--;
}
}
for (i = 0; i < n; i++) {
printf("%d ", a[i]);
}
return 0;
}
4. 希尔排序5. 选择排序和冒泡排序类似，和n-i次关键字之间比较，从n-i+1个记录中找到关键字最小的记录，并和第i个记录交换。
冒泡排序需要两两之间比较然后交换，简单选择排序则比较出最小值然后交换。
无论好坏，都需要比较n-1+n-2+…+1=n(n-1)/2次，最好交换0次，最差交换n-1次。
#include <stdio.h>
int main()
{
//初始化数组
int a[] = {3,5,1,9,2,6,4,8,7};
int i,j,temp,min;
//获取数组字段个数
int n = sizeof(a) / sizeof(int);
//升序
for (i = 0; i < n - 1; i++) {
min = i;
for (j = i + 1; j < n; j++) {
if (a[j] < a[min]) {
min = j;
}
}
if (min != i) {
temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}
for (i = 0; i < n; i++) {
printf("%d ", a[i]);
}
return 0;
}
|
