Java排序算法（一）

Java排序算法（一）

排序的基本概念和分类

1.1排序的定义　　

　　在《大话数据结构》中，排序定义为，假设含有n个记录的序列为{r1,r2,...,rn},其相应的关键字{k1，k2，...,kn}，需确定1,2...n的一种排列p1，p2...pn,是其相应的关键字满足Kp1<=Kp2<=...<=Kpn(非递减或非递增)关键，即使得序列称为一个按关键字有序的序列{rp1,rp2...rp3},这样的操作称为排序。

1.2排序的稳定性

　　假设ki=kj（1<=i<=n,1<=j<=n,i!=j）,且在排序前的序列中ri领先于rj（即i<j）。如果排序后ri仍然领先rj，则所用的排序方法是稳定的；反之， 若可能使得排序后序列中rj领先ri，则称所用的排序方法是不稳定的。如图所示：

1.3内排序和外排序

内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。
外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要内外多次交换数据才能进行
主要讨论内排序，排序算法性能主要受三方面影响
1.时间性能（尽可能少的关键字比较次数和尽可能少的记录移动次数）
2.辅助空间（执行算法所需要的其他存储空间）
3.算法复杂性（算法本身的复杂度，不是算法的时间复杂度）　

1.4七个主要的排序算法

按照算法的复杂性（可以简单理解为算法逻辑和算法编码量）
简单排序算法：冒泡排序，简单选择排序，直接插入排序
改进算法：快速排序，希尔排序，归并排序，堆排序

一、简单排序算法

public class Sort
{
    //实现从小到大排序
    public static void main(String[] args)
    {
        int[] arr1 = {9,1,5,8,3,7,4,6,2};
        //bubbleSort2(arr1);
        //selectSort(arr1);
        insertSort(arr1);
        for(int i=0;i<arr1.length;i++)
        {
            System.out.println(arr1[i]);
        }
    }
    /*
    *冒泡排序,相邻两个元素进行比较，如果满足条件进行位置置换
    *原理：本函数内循环一次，将最值提到冒泡到最尾部
    *备注：各位大雕可以写一个冒泡到数组头部的，我写冒泡到尾部代码看起来比较好记，哈哈
    *时间复杂度：比较1+2+3+...+n=n*(n+1)/2次，并做等数量级的记录移动O(n*n)
    */
    public static void bubbleSort1(int[] arr)
    {
    
        for(int i=0;i<arr.length-1;i++)
        {
            for(int j=0;j<arr.length-1-i;j++)
            {
                if(arr[j]>arr[j+1])
                {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
    /*
    *简单选择排序，以一个角标的元素和其他元素进行比较
    *原理，从n-1-i个记录中选出关键字最小的记录，并和第i个记录交换
    *时间复杂度：O(n*n)，相对而言，简单选择排序的性能要略优于冒泡排序
    */
    public static void selectSort(int[] arr)
    {
        for(int i=0;i<arr.length-1;i++)
        {
            int min = i;        //将当前下标定义为最小值下标
            for(int j=i+1;j<arr.length;j++)
            {
                //j初始化为i，表示每次都是数组arr下标为i的元素和后面（i+1）的元素进行比较
                if(arr[min]>arr[j])
                {
                    min = j;    //如果有小于当前最小值的关键字，此关键字下标赋值给min
                }
            }
            if(i!=min)            //如果min不等于i，说明找到最小值，交换
            {
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
    }
    /*
    *直接插入排序，
    *原理：将一个记录插入到已经排好序的有序表中，从而得到一个新的。记录数增加1的有序表
    *例子：《大话数据结构》中将其比作抽扑克牌，抽一张排序一张，好书推荐。。。
    *排序复杂度：O（n*n），直接插入排序比冒泡和简单选择排序的性能要好一些。
    */
    public static void insertSort(int[] arr)
    {
        int temp = 0;
        int j = 0;
        for(int i=1;i<arr.length;i++)
        {
            temp = arr[i];
            for(j=i;j>0&&temp<arr[j-1];j--)
            {
                arr[j] = arr[j-1];    //使得记录后移
            }
            arr[j] = temp;            //插入到正确位置
        }
    }
}