Java数据结构和算法笔记-简单排序算法

落日映苍穹つ 2022-06-09 12:51 270阅读 0赞

# Java数据结构和算法笔记-简单排序算法 #

本讲提到的排序算法都假定了数组作为数据存储结构，本讲所有算法的时间复杂度都是。在大多数情况下，假设当数据量比较小或基本上有序时，插入排序算法是三种简单排序算法中最好的选择，是应用最多的。对于更大数据量的排序来说，后面讲到的快速排序通常是最快的方法

## 1. 冒泡排序 ##

1）基本思想

> 在要排序的一组数中，对当前还未排好序的范围内的全部数，自下而上对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换

2）算法实现  
冒泡排序的Java代码：

// bubble sort
        public static void bubbleSort(long[] arr) {
            long temp;
            for(int i=0; i<arr.length-1; i++) { //outer loop (forward)
                for(int j=arr.length-1; j>i; j--) {
       //inner loop (backward)
                    if(arr[j] < arr[j-1]) { // swap them
                        temp = arr[j];
                        arr[j] = arr[j-1];
                        arr[j-1] = temp;
                    }
                }
            }
        }

测试冒泡排序及输出结果：

public void testBubbleSort() throws Exception {
            long[] arr = {
       79, 91, 13, 52, 34};
            Sort.bubbleSort(arr);
            System.out.println(Arrays.toString(arr));   //[13, 34, 52, 79, 91]
        }

## 2. 选择排序 ##

1）基本思想

> 在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。  
> 与冒泡排序相比，选择排序将必要的交换次数从O(N\*N)减少到O(N)，但比较次数仍然保持为O(N\*N)

2）算法实现  
选择排序的Java代码

// select sort
        public static void selectSort(long[] arr) {
            long temp;
            for(int i=0; i<arr.length-1; i++) { //outer loop
                int k = i; // location of minimum
                for(int j=i+1; j<arr.length; j++) { //inner loop
                    if(arr[j] < arr[k]) {
                        k = j; // a new minimum location
                    }
                }
                temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }

测试选择排序及输出结果：

public void testSelectSort() throws Exception {
            long[] arr = {
       79, 91, 13, 52, 34};
            Sort.selectSort(arr);
            System.out.println(Arrays.toString(arr));   //[13, 34, 52, 79, 91]
    
        }

## 3. 插入排序 ##

1）基本思想

> 在要排序的一组数中，假设前面(n-1)\[n>=2\]个数已经是排好顺序的（局部有序），现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。  
> 在插入排序中，一组数据仅仅是局部有序的；而冒泡排序和选择排序，一组数据项在某个时刻是完全有序的。

2）算法实现

插入排序的Java代码：

// insert sort
        public static void insertSort(long[] arr) {
            long temp;
            for(int i=1; i<arr.length; i++) { // i is marked location
                temp = arr[i]; // remove marked item
                int j = i; // start shifts at i
                while(j>=1 && arr[j-1]>temp) { // until one is smaller
                    arr[j] = arr[j-1]; // shift item right
                    j--;  // go left one position
                }
                arr[j] = temp; // insert marked item
            }
        }

测试插入排序以及输出结果：

public void testInsertSort() throws Exception {
            long[] arr = {
       79, 91, 13, 52, 34, 34};
            Sort.insertSort(arr);
            System.out.println(Arrays.toString(arr)); 
            //[13, 34, 34, 52, 79, 91]
        }