排序算法原理+实现（java）

排序算法

排序

冒泡排序

原理：两两比较相邻记录的关键码，反序则交换，每次交换出一个最大的或者最小的放在最终位置上，直到没有反序的记录为止。

辅助：

temp

解决的问题：

1.在一趟冒泡排序中，若有多个记录位于最终位置，如何记录？

2.如何使得已经位于最终位置的记录不再参与下一趟排序？

3.怎么判断排序结束？

实例：升序

初始序列50   13    55   97   27   38   49   65 

第一趟排序结果：13   50   55   27   38   49   65   97

第一趟详细过程：

50与13比较    50>13     交换：                   13   50   55   97   27   38   49   65 

50   < 55              不交换：13   50   55   97   27   38   49   65

55    < 97             不交换：13   50   55   97   27   38   49   65

97  >  27              交换：13   50   55   27  97   38   49   65

97 >  38               交换：13   50   55   27  38   97   49   65

97  >  49             交换：13   50   55   27  38   49   97   65

97 >  65               交换：13   50   55   27  38   49   65   97

第二趟排序结果：13   50   27   38   49   55  65   97

第三趟排序结果：13   27   38   50   49   55    65   97

第四趟排序结果：13   27   38   49    50   55    65   97

第五趟排序结果：13   27   38   49    50   55    65   97

第六趟排序结果：13   27   38   49    50   55    65   97

第七趟排序结果：13   27   38   49    50   55    65   97

第八趟排序结果：13   27   38   49    50   55    65   97

Java代码：

 public static void BubbleSort(int[] arr){
        System.out.println("BubbleSort");
        for(int j = 0;j < arr.length-1;j ++){
            //一趟冒泡排序
            for(int m = 0;m <arr.length-j-1 ;m ++){
                //m<7 arr[6]比较arr[7] 进行一趟就有一个被放在了最终位置上 所以有  -j
                if(arr[m] > arr[m+1]){
                    swap(arr,m,m+1);
                }

            }
        }
    }//BubbleSort

选择排序

原理：每次从未排序的序列中选择一个最小/大的放在最终位置上，再从剩下未排序的序列中选择一个次小的放在第二个位置上，以此类推

辅助：

minIndex

temp

java代码：

/**选择排序
 * 每一趟选择一个最小/最大的放在最终位置  然后再从未排序的序列中选择最小/大的放在第二个最终位置
 * @author 飞天小女警
 * @create 2020-11-15 21:59
 */
public class SelectionSortTest {
    public static void SelectionSort(int[]arr) {
        System.out.println("SelectionSort");

        int minIndex,temp;
        for(int i = 0;i <arr.length-1 ;i ++ ){
            minIndex = i;
            for(int j = i + 1;j < arr.length;j ++){
                if(arr[minIndex] > arr[j])
                    minIndex = j;
            }//for j
            if(minIndex !=i){
                temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }//if
        }//for
    }//SelectionSortTest
}//class

插入排序：

原理：构建有序序列，未排序的序列取第一个从后向前扫描有序序列，找到相应位置插入。

算法流程：

1.假定第一个元素有序

2.取第二个元素，在已排序的序列中从后向前扫描

3.若有序元素大于新元素，将有序元素移到下一个位置

4.重复3，直到有序元素小于或者等于新元素的位置

5.新元素插入

6.重复2~5

辅助：

int index;//从后向前扫描的索引
int currentNum;//当前要插入的num

java代码：

/**插入排序
 *通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
 * @author 飞天小女警
 * @create 2020-11-15 22:42
 */
public class InsertionSortTest {
    public static void InsertionSort(int []arr){
        System.out.println("InsertSort");

        int index;//从后向前扫描的索引
        int currentNum;//当前要插入的num

        for(int i = 1;i < arr.length; i++){//假设index是0 的已经有序 从index是1 的开始

            currentNum = arr[i];

            for(index = i -1;index >= 0 && arr[index] > currentNum; index--){

                    arr[index + 1] = arr[index];//后移
            }//for index
            //跳出循环 说明找到了位置
            // 但是index在判断不符合循环条件时候中已经在上一次循环中-1
                arr[index + 1] = currentNum;
        }//for i
    }//InsertionSort
}//class

希尔排序

原理：现将排序表分割成若干个形如L[i,i+d,i+2d,i+3d,...i+kd]的特殊子表，分别进行直接插入排序，当整个表已经基本有序时候对全体记录进行一次直接插入排序

算法流程：d1=n/2,di+1=di/2

1.先取一个小于N的步长d1，把表中全部记录分成d1个，所有距离d1的倍数的记录放在同一个组中

2.每个组中进行直接插入排序

3.去第二个步长d2<d1,重复过程，直到di=1，即所有记录都在同一个组中

4.进行一次直接插入排序

辅助：

Java代码：

归并排序

原理：

算法流程：

辅助：

快速排序

原理：

算法流程：

辅助：

堆排序

原理：

是一个，而堆排序是根据堆的这种数据结构设计的一种排序

大根堆和小根堆

性质：每个结点的值都大于其左孩子和右孩子结点的值，称之为大根堆；每个结点的值都小于其左孩子和右孩子结点的值，称之为小根堆

算法流程：

辅助：