排序算法

1.算法合集

1.一系列的计算步骤，用来将输入数据，转换成想要的输出结果。
2.算法用来解决特定问题，解决同一个问题不同算法的效率常常相差非常大。有时候差距的影响，比硬件和软件一样大。
3.排序算法，加密算法。
<一>排序算法
最常见的多项式时间算法复杂度关系为：
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3)
指数时间算法复杂度关系为：
O(2n) < O(n!)< O(nn)
http://www.docin.com/p-1338970704.html
空间换时间

时间换空间

https://blog.csdn.net/love_chenfeng/article/details/44066407

https://blog.csdn.net/u010402786/article/details/51435735

https://baike.baidu.com/item/%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/9664257?fr=aladdin

1.空间复杂度：

（1）是对一个算法在运行过程中临时占用存储空间大小的量度。而一般的递归算法就要有O(n)的空间复杂度了，

该算法所耗费的存储空间。

（2）一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。

（3）如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)；当一个算法的空间复杂度与n成线性比例关系时，可表示为O(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间。接下来一个一个分析。

2. 时间复杂度：

(1)冒泡排序：把小的向前移动，把大的元素向后移动。 复杂度0(N²) 空间复杂度 0(1). 不会随着n的增大，不会创建一定的变量。

336DEDCC-6DD4-459E-8122-FB73455E5DBC.png A75733A7-5261-4E8D-8D4D-93B227FE42EF.png

<2>快速排序 复杂度0(N²)
快速排序是对冒泡排序的改进.通过一趟排序将要排序的数据分割成对立的两部分，其中一部分的所有数据逗比另外一部分所有的数据小，
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
1.先从数列中取出一个数作为基准数。（一般是首元素，）
2.分区过程，将比这个数大的放右边 小于或者等于他的数放在它的左边。
3.对左右区间重复第二部，直到各个区间只有一个数。

>>>   i = 0   j=9.  基准数。21。   右边查找小于21的j的值赋给i。  ———      找到j=7   a[i] = a[j]    i=0. j=7
4      32        43        98      54    45     23   4  66  86
    >>>   i = 1   j=7.  基准数。21。  左边查找小于21的i 的值赋给j 。    ———    找到  i=1     j = 7,  a[j] = a[i] 
4      32        43        98      54    45     23   4  66  86
4      32        43        98      54    45     23   32     66  86
    >>>  i = 1    j=7  查找小于21的j.   右边查找小于21的j的值赋给i。  ———      找到j=1   i = 1
4      32        43        98      54    45     23   32     66  86
4      21        43        98      54    45     23   32     66  86              ———     a[i] = key;

回调。 sort(a,0, 0);
sort(a,2, 9);
>>> Key = 43——————右边查找小于43的j的值赋给i。——— I= 2 j = 9.
4 21 32 98 54 45 23 32 66 86 ——— j =7 I= 2 a[i] = a[j]
>>> Key = 43——————左边查找大于43的i 的值赋给j 。——— i= 3 j = 7
4 21 32 98 54 45 23 98 66 86
>>>Key = 43——————右边查找小于43的j的值赋给i。——— j = 6 i = 3
4 21 32 23 54 45 23 98 66 86
>>>Key = 43——————左边查找大于43的i 的值赋给j 。——— j = 6 i = 4
4 21 32 23 54 45 23 98 66 86
4 21 32 23 54 45 54 98 66 86
>>>Key = 43——————右边查找小于43的j的值赋给i。——— j =5 i = 4
查找小于43的23 j= 3 <i
a[i] = key;
4 21 32 23 43 45 54 98 66 86
回调。 sort(a,2, 3);
sort(a,5, 9);

86DD3F09B3A9FAFB4ED98E1A73CDCD36.png
BEDE5ABE3CA9107F6EE8C61CB4D009EB.png

<4>归并排序 又叫分治法，将排好序的子序列合并，得到完全有序的序列，

<5>希尔排序

<6>堆排序