排序算法

冒泡排序

实现思路：

• 两两比较相邻的关键码，如果反序则交换，直到没有反序的记录

快速排序

实现思路:

• 快速排序算是对冒泡排序算法的改进，从记录序列的两端向中间进行

两者的区别

---

由于冒泡排序是对相邻的数据进行两两比较，元素的移动次数和比较次数都比较多，而快速排序是从记录序列的两端向中间进行，所以在元素的移动次数和比较次数上都减少了

---

冒泡排序使用两层循环嵌套，具体代码省略
具体实现快速排序算法：

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、元素分布情况、元素信息量大小、使用的语言工具

小结

1. 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。
2. 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
3. 若n较大,则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序法中被认为是最好的方法。
4. 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlog2n)的时间。
5. 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。