数据结构中的内排序详解
数据结构中的内排序详解
(本文所有图片来自慕课网https://www.icourse163.org/learn/WHU-1001539003?tid=1002049010#/learn/content)
一、插入排序
基本原理：
（1）直接插入排序
一趟排序时，无序区中的R[i]插入有序区之后：
1、先和R[i-1]比较关键字大小，如果R[i]>R[i-1]就是正序的，不需要做 后面的比较了；如果R[i]<R[i-1]，则是反序，进行下一步。
2、设tmp=R[i]，j=i-1。
3、R【j】(即R[i-1])与tmp比较大小，R[j]<tmp,则R[j+1]=R[j]，
j=j-1。如此循环，直到R[j]>=tmp。
对应的算法如下：
（2）折半插入排序
采用折半查找方法找到插入的位置，就是折半插入排序。
（3）希尔排序
二、交换排序
（1）冒泡排序
举例：A B C D E
从最后一个往前冒泡，E和D比较，小的数据放在D里，D和C比较，小的放在C里，一直到A，此时A里的数据是最小的了。所以下一次从后往前的循环就不再和A比较了。算法如下：
–
其中的exchange是为了防止一个问题的发生——当第一轮冒泡就完成排序的话，程序不知道还是会继续运行。
（2）快速排序
举例：3 1 5 4 2
1：i,j分别指向头尾元素，找第一个关键字作为基准，单独拎出去
2：从后往前找，小于基准的数放到最前面
3：找到小于基准的值后，从前找大于基准的值放到最后
4：重复23步，直到i和j位置重合，然后将基准值放在i或者j处
5：将基准前后的两个数组，分别进行递归，继续排列。
算法：
三、选择排序
未完待续