排序的基本几种算法

排序基本上： 都是基于“交换”进行排序

冒泡排序
基本思想： 若排序表长N，从后往前（或从前往后）相邻的两两进行比较元素的值，若是逆序（即：a[i-1]>a[i]），就交换它们，直到序列比较完，====> 算一趟冒泡；
结果===>将最小的值替换到了最前面的一个位置；
下一趟冒泡时候，不用去比较前面一个得出结果的那个元素了；这样待排序的数目-1；
这样每次都是将最小的值放在当前序列的最前面，这样最多就是做了N-1 趟冒泡排序就拍好了；
时间复杂度是： (n-1) + (n-2)+……+1 = n*(n-1)/2 所以时间复杂度是O(n^2)；

冒泡排序
分析：
空间效率： 由于一般是需要一个辅助空间就可以了，所以空间复杂度是O(1);
时间效率： 比较次数： n *(n-1)/2 移动次数： 3n *(n-1)/2
所以，最坏的情况下时间复杂度是O(n^{2),平均时间复杂度为O(n}2);
稳定性： 由于当i >j 且a[i].key =a[j].key时，不会交换两个元素，所以冒泡排序是一个稳定的排序；
和选择排序的区别 ： 子序列对于全局序列也是有序的，而选择排序就不是了；

L
<font face="黑体">快速排序</font> ====> 对冒泡排序的进一步改进；基于分支法

思想：在待排序列表L[1…n]中任意取一个元素pivot作为基准，通过一系列排序将待排序表划分为独立的两个部分L[1…k-1]和L[k+1…n]，使得L[1…k-1]中所有元素小于pivot，L[k+1…n]小于pivot，L[K+1…n]中所有的元素大于或者等于pivot，则pivot放在其最终的位置L(k) 上，这个过程称作一趟快速排序。而后分别递归地对两个子表重复上述过程，直到每个部分只有一个元素或者空为止，即所有元素放在其最终的位置上；(这种说法有点晦涩)

2、快速排序： 就是分支法，将数组中去一个数字，一般去第一个为K值，对于一组记录，通过一趟排序之后，原来的数组会分成为两个部分，一部分比K值都小，一部分的值比K值都大，然后再对这两个部分的数据进行划分；划分出更小的进行排列；

步骤如下：
（1）分解： 将输入的n个数的数组，分成两个非空的子系列a[m…k]和a[k+1,…,n]，使得a[m,…,k]中任一个元素的值不大于a[k+1,…,n]中任意一个元素的值；。
………… ，a[m]，……，a[k]，a[k+1]，……a[n]中任意一个元素的值。
（2）递归求解：通过递归调用快速排序算法分别对a[m……k]和a[k+1,……,n]进行排序；
（3）合并：由于对分解出的两个子系列的排序是在当前的数组里面进行排序的，他们之间互相没有干扰，所以，排完序的各部分子系列是不影响其大小的关系，所以完成之后，数组上的数是拍好的。

数组的数据如下： {49，38，65，97，76，97，65，49}；

排序过程 c语言实现的算法 go语言实现的算法
c语言上面的实现
image.png

,

基本的查找方法

可以用数组或者链表来存储这个顺序结构，数据的顺序性等等没有要去；时间复杂度很大O(t)=n;