排序算法
冒泡排序
实现思路：
- 两两比较相邻的关键码，如果反序则交换，直到没有反序的记录
快速排序
实现思路:
- 快速排序算是对冒泡排序算法的改进，从记录序列的两端向中间进行
两者的区别
由于冒泡排序是对相邻的数据进行两两比较，元素的移动次数和比较次数都比较多，而快速排序是从记录序列的两端向中间进行，所以在元素的移动次数和比较次数上都减少了
冒泡排序使用两层循环嵌套，具体代码省略
具体实现快速排序算法：
public static void sortCore(int[] array,int startIndex,int endIndex) {
if(startIndex>=endIndex) {
return;
}
int boundary=boundary(array,startIndex,endIndex);//选择划分的Index值
//递归调用，对数组两部分排序
sortCore(array,startIndex,boundary-1);
sortCore(array,boundary+1,endIndex);
}
private static int boundary(int[] array, int startIndex, int endIndex) {
int standard=array[startIndex];//定义标准，一般取首值、中值或末值
int leftIndex=startIndex;//左指针
int rightIndex=endIndex;//右指针
while(leftIndex<rightIndex) {
while(leftIndex<rightIndex&&array[rightIndex]>=standard) {
rightIndex--;//找出右半部分小于标准的Index值
}
array[leftIndex]=array[rightIndex];//把小于的值赋值到左半部分
while(leftIndex<rightIndex&&array[leftIndex]<=standard) {
leftIndex++;//找出左半部分大于标准的Index值
}
array[rightIndex]=array[leftIndex];//赋值到右边
}
array[leftIndex]=standard;//标准值赋给左边
return leftIndex;//返回新的划分Index值
}
选择排序
- 每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中
- 特点是记录的移动次数少
inti,j;
for(i=0;i<r.length-1;i++){//对n个记录进行n-1趟的选择排序
index=i;//初始化第i趟选择排序的最小记录的指针
for(j=i+1;j<r.length;j++){//在无序区选取最小记录
if(r[j]<r[index]){
index=j;
}
}
if(index!=i){//将最小记录与r[i]交换
temp=r[i];
r[i]=r[index];
r[index]=temp;
}
}
几种排序算法的比较和选择
- 选取排序方法需要考虑的因素：待排序元素数量n、元素分布情况、元素信息量大小、使用的语言工具
小结
- 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。
- 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
- 若n较大,则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序法中被认为是最好的方法。
- 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlog2n)的时间。
- 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。
