Java 数据结构与算法

程序=数据结构+算法





数据结构

数据结构两种表现形式：
   逻辑结构
   存储结构

数据的逻辑结构按照数据元素之间相互关系的特性来分，分为四种结构：集合、线性结构、树形结构和图状结构

线性表、栈、队列属于线性结构
树和图属于非线性结构

数据的存储结构主要包括数据元素本身的存储以及数据元素之间关系表示。数据元素之间的关系在计算机中主要有两种不同的表示方法：顺序映像和非顺序映像

并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。

顺序存储结构的特点是：数据元素的存储对应于一块连续的存储空间，数据元素之间的前驱和后续关系通过数据元素在存储器中的相对位置来反映


顺序表的特点是逻辑上相邻的数据元素，物理存储位置也相邻，并且，顺序表的存储空间需要预先分配。

它的优点：

　　（1）方法简单，各种高级语言中都有数组，容易实现。

　　（2）不用为表示节点间的逻辑关系而增加额外的存储开销。

　　（3）顺序表具有按元素序号随机访问的特点。

缺点：

　　（1）在顺序表中做插入、删除操作时，平均移动表中的一半元素，因此对n较大的顺序表效率低。

　　（2）需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。


链式存储结构的特点是：数据元素的存储对应的是不连续的存储空间，每个存储节点对应一个需要存储的数据元素，元素之间的逻辑关系通过存储节点之间的链接关系反映出来。

在链表中逻辑上相邻的数据元素，物理存储位置不一定相邻，它使用指针实现元素之间的逻辑关系。并且，链表的存储空间是动态分配的。

它的优点：

　　插入、删除运算方便。

缺点：

　　（1）要占用额外的存储空间存储元素之间的关系，存储密度降低。存储密度是指一个节点中数据元素所占的存储单元和整个节点所占的存储单元之比。

　　（2）链表不是一种随机存储结构，不能随机存取元素。


顺序表与链表的优缺点正好相反，那么在实践应用中怎样选取存储结构呢？通常有以下几点考虑：

　　（1）顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MaxSize”要有合适的设定，设定过大会造成存储空间的浪费，过小造成溢出。因此，当对线性表的长度或存储规模难以估计时，不宜采用顺序表。然而，链表的动态分配则可以克服这个缺点。链表不需要预留存储空间，也不需要知道表长如何变化，只要内存空间尚有空闲，就可以再程序运行时随时地动态分配空间，不需要时还可以动态回收。因此，当线性表的长度变化较大或者难以估计其存储规模时，宜采用动态链表作为存储结构。

　　但在链表中，除数据域外还需要在每个节点上附加指针。如果节点的数据占据的空间小，则链表的结构性开销就占去了整个存储空间的大部分。当顺序表被填满时，则没有结构开销。在这种情况下，顺序表的空间效率更高。由于设置指针域额外地开销了一定的存储空间，从存储密度的角度来讲，链表的存储密度小于1.因此，当线性表的长度变化不大而且事先容易确定其大小时，为节省存储空间，则采用顺序表作为存储结构比较适宜。

　　（2）基于运算的考虑（时间）

　　顺序存储是一种随机存取的结构，而链表则是一种顺序存取结构，因此它们对各种操作有完全不同的算法和时间复杂度。例如，要查找线性表中的第i个元素，对于顺序表可以直接计算出a(i)的的地址，不用去查找，其时间复杂度为o(1).而链表必须从链表头开始，依次向后查找，平均需要o(n)的时间。所以，如果经常做的运算是按序号访问数据元素，显然顺序表优于链表。

　　反之，在顺序表中做插入，删除时平均移动表中一半的元素，当数据元素的信息量较大而且表比较长时，这一点是不应忽视的；在链表中作插入、删除，虽然要找插入位置，但操作是比较操作，从这个角度考虑显然后者优于前者。


　　总之，两种存储结构各有长短，选择哪一种由实际问题中的主要因素决定。通常“较稳定”的线性表，即主要操作是查找操作的线性表，适于选择顺序存储；而频繁做插入删除运算的（即动态性比较强）的线性表适宜选择链式存储。



一、线性结构(List)

线性结构是最简单，也是最常用的数据结构之一。线性结构的特点是：在数据元素的有限集中，除第一个元素无直接前驱，最后一个元素无直接后续以外，每个数据元素有且仅有一个直接前驱元素和一个直接后续元素。

线性表是一种抽象数据类型，数组是一种具体的数据结构。

线性表只是一个抽象的数据结构，并不具有具体的物理形式，线性表需要通过其他有具体物理形式的数据结构来实现。在线性表的具体实现中，表中相邻的元素不一定存储在连续的内存空间中，除非表是用数据来实现的。

线性表的顺序存储与实现：数组（ArrayList）

线性表的这种机内表示称作线性表的顺序存储，它的特点是：以数据元素在机内存储地址相邻来表示线性表中数据元素之间的逻辑关系。每一个数据元素的存储地址都和线性表的起始地址相差一个与数据元素在线性表中的序号成正比的常数。因此，只要确定了线性表的起始地址，线性表中的任何一个数据元素都可以随机存取。


线性表的链式存储与实现：双向链表（LinkedList）

线性表的这种机内表示称作线性表的链式存储，它的特点是：使用指针将存储线性表中数据元素的那些单元依次串联在一起。这种方法避免了再数组中用连续的单元存储元素的缺点，因而在执行插入或删除运算时，不再需要移动元素来腾出空间或填补空缺。然而我们为此付出的代价是，需要在每个单元中设置指针来表示表中元素之间的逻辑关系，因而增加了额外的存储空间的开销。

栈和队列是比数组和其他数据结构更加抽象的结构，是站在更高的层面对数据进行组织和维护。

栈

栈的主要机制可用数组来实现，也可以用链表来实现

栈（stack）又称堆栈，它是运算受限的线性表，其限制是仅允许在表的一端进行插入和删除操作，不允许在其他任何位置进行插入、查找、删除等操作。

由于栈的插入和删除操作仅在栈顶进行，后进栈的元素必定先出栈，所以又把堆栈成为后进先出表（Last In First Out,LIFO）


队列

队列(queue)简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端（队尾）进行插入，而在表的另一端（队首）进行删除。

由于队列的插入和删除操作分别在队尾和队首进行，每个元素必然按照进入的次序离队，也就是说先进队的元素必然先离队，所以称队列为先进先出表（First In First Out,FIFO）。


二、非线性结构

树

在树结构中数据元素之间的逻辑关系是前驱唯一而后续不唯一，即数据元素之间是一对多的关系。

树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个节点称为该树的根结点，或简称为树根。

图

图是一种较线性结构和树结构更为复杂的数据结构，在图结构中数据元素之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。



算法

算法设计是最具创造性的工作之一，人们解决任何问题的思想、方法和步骤实际上都可以认为是算法。

算法(algorithm)是指令的集合，是为解决特定问题而规定的一系列操作。它是明确定义的可计算过程，以一个数据集合作为输入，并产生一个数据集合作为输出。一个算法通常来说具有以下五个特性：
1.输入：一个算法应以待解决的问题的信息作为输入
2.输出：输入对应指令集处理后得到的信息
3.可行性：算法是可行的，即算法中的每一条指令都是可以实现的，均能在有限的时间内完成
4.有穷性：算法执行的指令个数是有限的，每个指令又是在有限时间内完成的，因此整个算法也是在有限时间内可以结束的。
5.确定性：算法对于特定的合法输入，其对应的输出是唯一的。即当算法从一个特定输入开始，多次执行同一指令集结果总是相同的。

对于随机算法，算法的第五个特性应当被放宽。

在计算机资源中，最重要的就是时间和空间。评价一个算法性能的好坏，实际上就是评价算法的资源占用问题。


一、递归

递归(recursion)是指在定义自身的同时有出现了对自身的应用。如果一个算法直接或间接地调用自己，则称这个算法是一个递归算法。

任何一个有意义的递归算法总是由两部分组成：递归调用与递归终止条件。

【每个递归函数都有两部分：基线条件（base case）和递归条件（recursive case）。
递归条件指的是函数调用自己，
基线条件则指的是函数不再调用自己，从而避免形成无限循环。】

递归调用的基本法则：

1.基准情形：必须总要有某些基准的情形，他们不用递归就能求解

2.不断推进：对于某些要递归求解的情形，递归调用必须总能够朝着一个基准情形推进

3.设计原则：假设所有的递归调用都能运行

4.合成效益法则：在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作。

    public static int f(int x)
    {
          if(x==0)       //基准情形
              return 0;
          else
              return 2*f(x-1)+x*x;

    }


二、查找


基于线性结构的查找主要介绍两种最常见的查找方法：顺序查找和折半查找

顺序查找：

特点：用所给的关键字与线性表中各元素的关键字逐个进行比较，知道成功或失败
缺点：平均查找长度较大，特别是当n较大时，查找效率较低
优点：算法简单且适应面广，对查找表的结构没有要求，无论数据元素是否按照关键字有序或无序均适用。

折半查找：
这种查找方法需要待查的查找表满足两个条件：首先，查找表必须适用顺序的存储结构，其次，查找表必须按照关键字大小有序排列

算法的基本思想是：首先，将查找表中间位置数据元素的关键字与给定关键字比较，如果相等则查找成功，否则利用中间元素将表一分为二，如果中间元素关键字大于给定关键字，则在前一子表中进行折半查找，否则在后一子表中进行折半查找。重复以上过程，知道找到满足条件的元素，则查找成功；或直到子表为空为止，此时查找不成功。

用二分查找最多需要logn步,时间复杂度为：O(logn)

public class BinarySearch {

        //方法一：非递归折半查找：
        private static void binarySearch(int a[],int k) {
                int low=0;
                int high=a.length-1;
                int mid;

                while (low<=high) { 

                       mid=low+(high-low)/2;

                        if (k==a[mid]) {
                               System.out.println(a[mid]+"在"+mid+"位置");
                               return;
                        }else {
                               if (k<a[mid]) {

                                       high=mid-1;
                                }
                                else {

                                       low=mid+1;
                                }
                        }
                }
                System.out.println("无法查找到该元素！");
        }

        //方法二：使用递归的折半查找
        private static int binarySearch(int a[],int k,int low,int high ) {
                if (a.length<=0) {
                        System.out.println("数组内元素为空！");
                        return -1;
                }
                if (low>high) {
                        System.out.println("无法查找到该元素！");
                        return -1;
                }else {
                        //代码中 low + (high - low) / 2 就和 (low + high) / 2 的结果相同，但是有效防止了 low 和 high 太大直接相加导致溢出

                        int mid=low+(high-low)/2;
                        if (k==a[mid]) {
                              System.out.println(a[mid]+"在"+mid+"位置");
      return mid;
                        }else {
                                if (k<a[mid]) {
                                     return binarySearch(a, k, low, mid-1);
                                }else {
                                     return binarySearch(a, k, mid+1, high);
                                }
                        }
               }
        }


       public static void main(String[] args) {
                int a[]={1,2,3,4,5,6,7};
                System.out.println("非递归算法：");
                binarySearch(a, 1);
                binarySearch(a, 2);
                binarySearch(a, 3);
                binarySearch(a, 4);
                binarySearch(a, 5);
                binarySearch(a, 6);
                binarySearch(a, 7);
                System.out.println("递归算法：");
                binarySearch(a, 1, 0, a.length-1);
                binarySearch(a, 2, 0, a.length-1);
                binarySearch(a, 3, 0, a.length-1);
                binarySearch(a, 4, 0, a.length-1);
                binarySearch(a, 5, 0, a.length-1);
                binarySearch(a, 6, 0, a.length-1);
                binarySearch(a, 7, 0, a.length-1);
        }
}



三、排序


排序分为：插入排序、交换排序、选择排序、归并排序

插入排序：

插入排序的基本排序思想是：逐个考察每个待排序元素，将每一个新元素插入到前面已经排好序的序列中适当的位置上，使得新序列仍然是一个有序序列。

1）直接插入排序：

是一种简单的插入排序方法，它的基本思想是：仅有一个元素的序列总是有序的，因此，对n个记录的序列，可从第二个元素开始直到第n个元素，逐个向有序序列中执行插入操作，从而得到n个元素按关键字有序的序列


public class InsertSort {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int a[] = {3,1,5,7,2,4,9,6};
        new InsertSort().insertSort(a);
    }
    /**
     * 直接插入排序算法的实现
     * @param a
     */
    private void insertSort(int[] a) {
        // TODO Auto-generated method stub
        System.out.println("——————直接插入排序算法—————");
        int n = a.length;
        int i,j;
        for(i=1;i<n;i++){
            /**
             * temp为本次循环待插入有序列表中的数
             */
            int temp = a[i];
            /**
             * 寻找temp插入有序列表的正确位置
             */
            for(j=i-1;j>=0 && a[j]>temp;j--){
                /**
                 * 元素后移，为插入temp做准备
                 */
                a[j+1] = a[j];
            }
            /**
             * 插入temp
             */
            a[j+1] = temp;
            print(a,n,i);
        }
        printResult(a,n);
    }
    /**
     * 打印排序的最终结果
     * @param a
     * @param n
     */
    private void printResult(int[] a, int n){
        System.out.print("最终排序结果：");
        for(int j=0;j<n;j++){
            System.out.print(" "+a[j]);
        }
        System.out.println();
    }
    /**
     * 打印排序的每次循环的结果
     * @param a
     * @param n
     * @param i
     */
    private void print(int[] a, int n, int i) {
        // TODO Auto-generated method stub
        System.out.print("第"+i+"次：");
        for(int j=0;j<n;j++){
            System.out.print(" "+a[j]);
        }
        System.out.println();
    }
}

时间复杂度为O(n^2)

2）折半插入排序：

直接插入排序的基本操作是向有序序列中插入一个元素，插入位置的确定是通过对有序序列中元素按关键字逐个比较得到的。既然是在有序序列中确定插入位置，则可以不断二分有序序列来确定插入位置，即搜索插入位置的方法可以使用折半查找实现。


public class InsertSort {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int a[] = {3,1,5,7,2,4,9,6};
        new InsertSort().binaryInsertSort(a);
    }
   
    /**
     * 折半插入排序算法的实现
     * @param a
     */
    private void binaryInsertSort(int[] a) {
        // TODO Auto-generated method stub
        System.out.println("——————折半插入排序算法——————");
        int n = a.length;
        int i,j;
        for(i=1;i<n;i++){
            /**
             * temp为本次循环待插入有序列表中的数
             */
            int temp = a[i];
            int low=0;
            int high=i-1;
            /**
             * 寻找temp插入有序列表的正确位置，使用二分查找法
             */
            while(low <= high){
                /**
                 * 有序数组的中间坐标，此时用于二分查找，减少查找次数
                 */
                int mid = (low+high)/2;
                /**
                 * 若有序数组的中间元素大于待排序元素，则有序序列向中间元素之前搜索，否则向后搜索
                 */
                if(a[mid]>temp){
                    high = mid-1;
                }else{
                    low = mid+1;
                }
            }
           
            for(j=i-1;j>=low;j--){
                /**
                 * 元素后移，为插入temp做准备
                 */
                a[j+1] = a[j];
            }
            /**
             * 插入temp
             */
            a[low] = temp;
            /**
             * 打印每次循环的结果
             */
            print(a,n,i);
        }
        /**
         * 打印排序结果
         */
        printResult(a,n);
    }
    /**
     * 打印排序的最终结果
     * @param a
     * @param n
     */
    private void printResult(int[] a, int n){
        System.out.print("最终排序结果：");
        for(int j=0;j<n;j++){
            System.out.print(" "+a[j]);
        }
        System.out.println();
    }
    /**
     * 打印排序的每次循环的结果
     * @param a
     * @param n
     * @param i
     */
    private void print(int[] a, int n, int i) {
        // TODO Auto-generated method stub
        System.out.print("第"+i+"次：");
        for(int j=0;j<n;j++){
            System.out.print(" "+a[j]);
        }
        System.out.println();
    }
}


时间复杂度 ： O(n^2)

空间复杂度 ： O(1)

在插入排序中，经过每一轮的排序处理后，数组前端的数是排好序的。


3）希尔排序：

希尔排序的基本思想是：首先将待排序的元素分为多个子序列，使得每个子序列的元素个数相对较少，个各个子序列分别进行直接排序，待整个待排序序列“基本有序”后，再对所有元素进行一次直接插入排序

public class ShellSortTest2 {
   /**
    * 待排序的数组
    */
   private int[] sources;
   /**
    * 数组内元素个数
    */
   private int itemsNum;
   /**
    * 增量数组序列
    */
   private int[] intervalSequence;
 
   /**
    * @param maxItems
    *   数组大小
    * @param intervalSequence
    *   增量数组序列
    */
   public ShellSortTest2(int[] source, int[] intervalSequence) {
      this.sources = new int[source.length];
      this.itemsNum = 0;// 还没有元素
      this.intervalSequence = intervalSequence;
   }
 
   /**
    * 希尔排序算法
    */
   public void shellSort() {
      int gap = 0;// 为增量
      for (int iIntervalLength = 0; iIntervalLength < intervalSequence.length; iIntervalLength++)// 最外层循环，由增量序列元素个数决定
     {
         gap = intervalSequence[iIntervalLength]; // 从增量数组序列取出相应的增长序列
         int innerArraySize;// 每次内部插入排序的元素个数
         if (0 == itemsNum % gap) {
               innerArraySize = itemsNum / gap;
         } else {
               innerArraySize = itemsNum / gap + 1;
         }
    for (int i = 0; i < gap; i++) {
           int temp = 0;
           int out = 0, in = 0;
           if (i + (innerArraySize - 1) * gap >= itemsNum) {
              innerArraySize--;
           }
         // 内部用插入排序
        for (int j = 1; j < innerArraySize; j++) {
              out = i + j * gap;
              temp = sources[out];
              in = out;
              while (in > gap - 1 && sources[in - gap] > temp) {
                 sources[in] = sources[in - gap];
                 in = in - gap;
              }
            sources[in] = temp;
          }
       }
       System.out.print("增长序列为: " + gap + " ");
       this.displayArray();
      }
   }
 
   /**
    * 初始化待排序数组
    */
   public void initArray(int[] array) {
      for (int i = 0; i < array.length; i++) {
        sources[i] = array[i];
      }
      itemsNum = array.length;
   }
 
   /**
    * 显示数组内容
    */
   public void displayArray() {
      for (int i = 0; i < itemsNum; i++) {
         System.out.print("\t" + sources[i] + " ");
      }
      System.out.println("\n");
   }
 
   public static void main(String[] args) {
      int[] intervalSequence = { 5, 3, 1 };
      int[] source = { 49, 38, 65, 97, 76, 13, 27, 49, 55, 04 };
      ShellSortTest2 ss = new ShellSortTest2(source, intervalSequence);
      // 初始化待排序数组
      ss.initArray(source);
      System.out.print("原始序列： ");
      ss.displayArray();
      // 希尔排序
      ss.shellSort();
 
      System.out.print("最后结果： ");
      ss.displayArray();
   }
}


时间复杂度为O(n^3/2)


交换类排序

交换类排序主要是通过两两比较待排元素的关键字，若发现与排序要求相逆，则“交换”之。

1）起泡排序

起泡排序的思想是：首先，将n个元素中的第一个和第二个进行比较，如果两个元素的位置为逆序，则交换两个元素的位置；进而比较第二个和第三个元素关键字，如此类推，直到比较第n-1个元素和第n个元素为止；这是第一趟排序过程，在第一趟排序过程中，我们将关键字最大的元素通过交换操作放到了具有n个元素的序列的最一个位置上。然后进行第二趟排序，在第二趟排序过程中对元素序列的前n-1个元素进行相同操作，其结果是将关键字次大的元素通过交换放到最二个位置上。一般来说，第i趟排序是对元素序列的前n-i+1个元素进行排序，排序共进行n-1趟，即可使得元素序列按关键字有序。


public class BubbleSort {

public void bubbleSort(int[] nums){

        //用来标记每轮遍历中是否发生了交换
        boolean hasChange=true;

        int count=0;
        int temp=0;
        //每轮遍历开始，将hasChange设置为false
        for(int i=0;i<nums.length-1 && hasChange;i++){
              hasChange=false;
              for(int j=0;j<nums.length-1-i;j++){
                    if(nums[j]>nums[j+1]){
                         temp=nums[j+1];
                         nums[j+1]=nums[j];
                         nums[j]=temp;
                         hasChange=true;
                         count+=1;
                    }
                   
              }
        }
       
        System.out.println("loop count="+count);
        for(int num : nums)
        {
        System.out.println(num);
        }
           
   }
  
  
   public static void main(String[] args){
  
   int nums[]={9,8,7,6,5,4,3,2,1};
  
   BubbleSort sort=new BubbleSort();
  
   sort.bubbleSort(nums);
  
   }
  
}


空间复杂度为O(1)

时间复杂度为O(n^2)

在冒泡排序中，经过每一轮的排序处理后，数据后端的数是排好序的。


2）快速排序

快速排序的基本思想是：通过一个枢轴元素将n个元素的序列分为左、右两个子序列Ll和Lr,其中序列Ll中的元素均比枢轴元素小，而子序列Lr中的元素均比枢轴元素大，然后对左、右子序列分别进行快速排序，再将左、右子序列排好序后，则整个序列有序，而对左右子序列的排序过程直到子序列中只包含一个元素时结束，此时左、右子序列只包含一个元素则自然有序。

快速排序是将分治法运用到排序问题中的一个典型例子。

空间复杂度 ： O(logn)
时间复杂度 ： O(nlogn)

public class QuickSort {

    public static void quickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>high){
            return;
        }
        i=low;
        j=high;
        //temp就是基 准 位
        temp = arr[low];

        while (i!=j) {

            //要先从右往左找，依次往左递减，【顺序很重要，要先从右往左找】
            while (arr[j]>=temp&&i<j) {
                j--;
            }
            //再从左往右找，依次往右递增，
            while (temp>=arr[i]&&i<j) {
                i++;
            }
    
            if (i<j) {  //交换两个数在数组中的位置
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }

        }

        //最终将基准数归位，将基准为与i和j相等位置的数字交换
         arr[low] = arr[i];
         arr[i] = temp;

        //递归调用左半数组
        quickSort(arr, low, j-1);
        //递归调用右半数组
        quickSort(arr, j+1, high);
    }


    public static void main(String[] args){
        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
        quickSort(arr, 0, arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}


package sort;

/**
* 快速排序
* 不稳定，时间复杂度 最理想 O(nlogn) 最差时间O(n^2)
*/
public class QuickSort {

    private static int[] quickSort(int[] a, int low, int high) {
       
        //中心点
        int mid = 0;
        if (low < high) {
            mid = partition(a, low, high);
            quickSort(a, low, mid - 1);
            quickSort(a, mid + 1, high);
        }
        return a;
    }

    private static int partition(int[] a, int low, int high) {

        int i=low,j=high,privot = a[low],t;  //pivot基准元素

        while (i!=j) {
            while (i<j && a[j] > privot) {  //顺序很重要，要先从右往左找
                j--;
            }
           
            while (i<j && a[i] <= privot) {  //再从左往右找
                i++;
            }

            if(i<j){  //当哨兵i 和 哨兵j 没有相遇时，交换两个数在数组中的位置
           
                    t = a[j];
                    a[j] = a[i];
                    a[i] = t;
           }
        }
     
        //最终将基准数归位，将基准为与i和j相等位置的数字交换
        a[low] = a[i];
        a[i]=privot;

        return i;

    }

    //测试
    public static void main(String[] args) {
        int[] a = {1, 14, 6, 8, 99, 9, 2, 99};
        int[] sort = quickSort(a, 0, 7);
        for (int s : sort) {
            System.out.print(s + " ");
        }
    }

}


快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。





选择类排序

1）简单选择排序

简单选择排序的基本思想是：
第一趟，从 n 个元素中找出关键字最小的元素与第一个元素交换；
第二趟，在从第二个元素开始的 n-1 个元素中再选出关键字最小的元素与第二个元素交换；
如此，第 k 趟，则从第 k 个元素开始的 n-k+1 个元素中选出关键字最小的元素与第 k 个元素交换，直到整个序列按关键字有序。

public class TestSelectSort {
        public static void sort(int arr[]) {
                int temp = 0;
                for (int i = 0; i < arr.length - 1; i++) {
                        // 认为目前的数就是最小的, 记录最小数的下标
                        int minIndex = i;
                        for (int j = i + 1; j < arr.length; j++) {
                               if (arr[minIndex] > arr[j]) {
                                        // 修改最小值的下标
                                        minIndex = j;
                                }
                        }
                        // 当退出for就找到这次的最小值
                        if (i != minIndex) {
                                temp = arr[i];
                                arr[i] = arr[minIndex];
                                arr[minIndex] = temp;
                        }
               }
        }

        public static void main(String[] args) {
               int arr [] = {26, 53,48,11,13,48,32,15};
               sort(arr);
               System.out.println(Arrays.toString(arr));
        }
}





时间复杂度为O(n^2)


2）堆排序


public class HeapSort {

public void HeapAdjust(int[] array, int parent, int length) {

int temp = array[parent]; // temp保存当前父节点

int child = 2 * parent + 1; // 先获得左孩子



while (child < length) {

// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点

if (child + 1 < length && array[child] < array[child + 1]) {

child++;

}



// 如果父结点的值已经大于孩子结点的值，则直接结束

if (temp >= array[child])

break;



// 把孩子结点的值赋给父结点

array[parent] = array[child];



// 选取孩子结点的左孩子结点,继续向下筛选

parent = child;

child = 2 * child + 1;

}



array[parent] = temp;

}



public void heapSort(int[] list) {

// 循环建立初始堆

for (int i = list.length / 2; i >= 0; i--) {

HeapAdjust(list, i, list.length - 1);

}



// 进行n-1次循环，完成排序

for (int i = list.length - 1; i > 0; i--) {

// 最后一个元素和第一元素进行交换

int temp = list[i];

list[i] = list[0];

list[0] = temp;



// 筛选 R[0] 结点，得到i-1个结点的堆

HeapAdjust(list, 0, i);

System.out.format("第 %d 趟: \t", list.length - i);

printPart(list, 0, list.length - 1);

}

}
}



归并排序

归并排序的基本思想是基于合并操作，即合并两个已经有序的序列是容易的，不论这两个序列是顺序存储还是链式存储，合并操作都可以在O(m+n)时间内完成。

归并排序的过程：

1.划分：将待排序的序列划分为大小相等（或大致相等）的两个子序列
2.治理：当子序列的规模大于1时，递归排序子序列，如果子序列规模为1则成为有序序列
3.组合：将两个有序的子序列合并为一个有序序列

时间复杂度 ：O(n log n)

空间复杂度 ：O(n)





public class MergeSort {

    //两路归并算法，两个排好序的子序列合并为一个子序列
    public void merge(int []a,int left,int mid,int right){
        int []tmp=new int[a.length];//辅助数组
        int p1=left,p2=mid+1,k=left;//p1、p2是检测指针，k是存放指针

        while(p1<=mid && p2<=right){
            if(a[p1]<=a[p2])
                tmp[k++]=a[p1++];
            else
                tmp[k++]=a[p2++];
        }

        while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
        while(p2<=right) tmp[k++]=a[p2++];//同上

        //复制回原素组
        for (int i = left; i <=right; i++)
            a[i]=tmp[i];
    }

    public void mergeSort(int [] a,int start,int end){
        if(start<end){//当子序列中只有一个元素时结束递归
            int mid=(start+end)/2;//划分子序列
            mergeSort(a, start, mid);//对左侧子序列进行递归排序
            mergeSort(a, mid+1, end);//对右侧子序列进行递归排序
            merge(a, start, mid, end);//合并
        }
    }

    @Test
    public void test(){
        int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
        mergeSort(a, 0, a.length-1);
        System.out.println("排好序的数组：");
        for (int e : a)
            System.out.print(e+" ");
    }
}