国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

常見排序算法及其實現(Binary，Insert、Select、Quick、Bubble.etc.S

187J3X1 / 1390人閱讀

摘要：常見排序算法及其實現說明如果有幸能看到本文中的代碼是參考編程思想某培訓機構。若兩個記錄和的關鍵字相等，但排序后的先后次序保持不變，則稱為這種排序算法是穩定的。

常見排序算法及其實現 說明

如果有幸能看到

1、本文中的代碼是參考《Java編程思想》、某培訓機構。

2、文中的代碼放Github了，有興趣的可以看看，點個star鼓勵下我。

3、代碼在Sublime中敲的，坑爹的GBK，注釋了很多中文，一轉碼不能用了?。。?/p>

4、重點在思想，而不是實現 。再次推薦《Java編程思想》

5、如有拼寫錯誤，還請諒解。本文只為自己復習使用，最后放了兩個收藏非常有水準的文章鏈接。

數據結構之排序

排序：假設含有n個記錄的序列{R1,R2,R3..,Rn}，其中的關鍵字序列為{K1,K2,K3...,Kn}。將這些記錄重新排序為{Ri1,Ri2,Ri3,Rin} ,使得相應的關鍵字滿足Ki1<=Ki2<=..<=Kim,這樣的一種操作被稱為排序。

通常來說，排序的目的是快速查找

衡量排序算法的優勢：

1、時間復雜度：分析關鍵字的比較次數和記錄的移動次數。

2、空間復雜度：分析排序算法中需要多少輔助內存。

3、若兩個記錄A和B的關鍵字相等，但排序后A、B、的先后次序保持不變，則稱為這種排序算法是穩定的。

排序算法分類：內部排序和外部排序

內部排序：整個排序過程不需要借助于外部存儲器(如此攀等)，整個排序在內存中完成。

外部排序：參與排序的數據非常多，數據量非常大，計算機無法把整個排序過程放在內存中完成，必須借助于外部存儲器，外部排序最常見的是多路歸并排序，可以認為外部排序由多次內部所組成。

常用的內部排序

選擇排序

直接選擇排序

堆排序

交換排序

冒泡排序

快速排序

插入排序

直接插入、折半插入

歸并排序

桶式排序

基數排序

選擇排序

基本原理：
將待排序的元素分為已排序和未排序，依次將為排序的元素中最小的元素放入已排序的組中，

直接排序簡單直觀，但性能略差：堆排序是一種較為搞笑的選擇排序。但實現起來略為復雜。

代碼實現：

import java.util.Arrays.*;
//選擇排序,
public class SelectSort{
    public static void selectSort(int[] data) {

        int arrayLength = data.length;
        for (int i = 0; i < arrayLength - 1 ; i++ ) {
            for (int j= i +1; j < arrayLength; j++ ) {
                if (data[i] > data[j]) {
                    swap(data,i,j);
                }
            }
        }
        System.out.println("排序后 " + java.util.Arrays.toString(data));


    }

  //第一種通過臨時變量來完成交換
  //注意這里可以用另外一中一種方式
    static void swap(int[] data,int i,int j) {
            int tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }


    public static void main(String[] args) {
        int[] data = {3,4,2,6,8,1,9};
        selectSort(data);
    }
}

改進版的選擇排序：

//選擇排序算法
//選擇排序算法
//1、主要思想就是每次假設一個最小的值
public class SelectSort1 {
    public static void selectSort1(int[] data) {
        int arraylength = data.length;
        for (int i = 0; i < arraylength - 1; i++ ) {
            int minIndex = i;      //每次假設一個最小值下標
            for (int j = i + 1; j < arraylength ; j++ ) {
                if (data[minIndex] > data[j]) {
                minIndex = j;
                }
            }
            //判斷需要交換的下標是否為自己
            if (minIndex != i) {
                 data[minIndex] = data[minIndex] + data[i];
                 date[i] = date[minIndex] - data[i];
                 data[minIndex] = data[minIndex] - data[i];
            }

        }
        //輸出結果
        for (int d :data ) {
            System.out.println("排序之后：" + d);
        }
    }

    public static void main(String[] args) {
        int[] data = {3,4,2,6,8,1,9};
        selectSort1(data);
    }
}

直接選擇排序效率分析

算法的時間效率：無論初始化狀態如何，在第i趟排序中選擇最小的元素，需要n-1次比較

算法的空間效率：空間效率較高，只需要一個附加程序單元用于交換，其空間效率為O(1)

算法的穩定性：不穩定

堆排序

資料和代碼來自這家，有一種感覺，年代越遠，越重視基礎?，F在的培訓呢？

堆排序就是把最大堆堆頂的最大數取出，將剩余的堆繼續調整為最大堆，再次將堆頂的最大數取出，這個過程持續到剩余數只有一個時結束

最大堆調整（Max-Heapify）：將堆的末端子節點作調整，使得子節點永遠小于父節點

創建最大堆（Build-Max-Heap）：將堆所有數據重新排序，使其成為最大堆

堆排序（Heap-Sort）：移除位在第一個數據的根節點，并做最大堆調整的遞歸運算

這個有點難啊，下一個?；貋碓賮砜?。

冒泡排序

相鄰兩元素進行比較，如有需要則進行交換，每完成一次循環就將最大元素排在前面(從小到大排序)下一次循環是將其他的數進行類似的比較。

代碼實現：

//冒泡排序
public class BubbleSort {
    static void sort(int[] data) {
        int len = data.length;
        for (int i = 0; i < len - 1; i++ ) {
            for (int j = 0 ; j < len - 1 - i; j++ ) {
                if (data[j] > data[j + 1]) {
                    swap(data,j,j+1);
                }
            }
        }

    }
    static void swap(int[] data,int i,int j) {
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }

    public static void main(String[] args) {
        int[] data = {4,2,6,8,2,1,0};
        sort(data);
        for(int d : data) {
            System.out.print("->" + d);
        }
    }
}

冒泡排序效率分析：

算法的時間效率：從冒泡排序的算法可以看出，若待排序的元素為正序，則只需進行一趟排序，比較次數為n-1次，移動元素次數為0；若待排序的元素為逆序，則需要進行n-1趟排序.

算法的空間效率：空間效率很高，只需要一個附加程序單元用于交換，其空間效率為O(1)

算法的穩定性：穩定

快速排序

快速排序(Quick Sorting)基本思想是：任取待排序序列中的某個元素為界點，通過一次劃分，將待排序元素分為左右兩個子序列，左子序列元素的排列序列均小于界點元素的排序碼，右子序列的排序碼則大于或等于界點的排序碼，然后分別對兩個字序列繼續進行劃分，直至每一個序列只有一個元素為止。

一定要認真啊，認真啊，認真?。。?！
代碼實現：

//快速排序
public class QuickSort {
    private static void swap(int[] data,int i,int j) {
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }

    private static void subSort(int[] data,int start,int end) {
        if (start < end) {
         int base = data[end];

         int i = start;
         int j = end + 1;

         while(true) {
             while(i < end && data[++i] <= base) ;
             while(j > start && data[--j] >= base);
             if (i > j) {
                 swap(data,i,j);
             }else {
                 break;
            }
        }

            swap(data, start, j);
            subSort(data, start, j - 1);
            subSort(data, j + 1, end);
        }

    }
    public static void quickSort(int[] data) {
        subSort(data,0,data.length - 1);
    }

    public static void main(String[] args) {
        int[] data = {9,5,6,88};
        quickSort(data);
        System.out.print(java.util.Arrays.toString(data));
    }
}

插入排序

基本思想：每次將一個待排序的元素，按其關鍵字的大小插入到前面已經排好序的子序的合適位置，直到全部記錄插入完成。

* 插入算法.
* 1,從后向前找到合適的位置插入
* 基本思想：每步將一個待排序的記錄，按其順序碼大小插入到前面已經排好的子序列的合適位置
* 直到全部插入為止
*/
public class InsertSort {
   public static void main(String[] args) {
       //待排序的數列
       int[] nums = {43, 23, 64, 24, 34, 78, 32};
       //控制比較的輪數
       for (int i = 1; i < nums.length; i++) {
           //記錄操作數
           int temp = nums[i];
           int j = 0;
           for (j = i - 1; j >= 0; j--) {
               //后一個和前一個比較，如果前面的大，則把前面的賦值到后面。
               if (nums[j] > temp) {
                   nums[j+1] = nums[j];
               } else {
                   break;
               }
           }
           if (nums[j + 1] != temp) {
               nums[j + 1] = temp;
           }
       }
       //輸出結果
       for(int n : nums) {
           System.out.println(n);
       }
   }
}

直接插入排序：

直接插入排序 的基本思想：把n個待排序的元素堪稱為一個有序表和無序表，開始時有序表中只包含一個元素，無序表中有n-1個元素，排序過程中每次從無序表中取出第一個元素的排序碼進行比較，將它插入到有序表中的適當位置，使之成為新的有序表。

代碼實現：

//直接插入排序
public class InsertSort {
    public static void insertSort(int[] data) {
        int arrayLength = data.length;
        for (int i = 1; i < arrayLength; i++) {
            int tmp = data[i];

            if (data[i] < data[i -1]) {
                int j = i - 1;
                for (;j >=0 && data[j] > tmp; j-- ) {
                    data[j + 1] = data[j];
                }
                data[j + 1] = tmp;
            }

        }
    }
    public static void main(String[] args) {
        int[] data = {5,2,6,9};
        insertSort(data);
        for (int d :data ) {
            System.out.print(" " + d);

        }
    }
}

折半插入排序

折半插入排序是對直接插入排序的簡單改進。

此處介紹的折半插入，其實就是通過不斷地折半來快速確定第i個元素的插入位置，這實際上是一種查找算法：折半查找。Java的Arrays類里的binarySearch()方法，就是折半查找的實現，用于從指定數組中查找指定元素，前提是該數組已經處于有序狀態。

與直接插入排序的效果相同，只是更快了一些，因為折半插入排序可以更快地確定第i個元素的插入位置

代碼實現：

//折半插入排序
public class BinaryInsertSort{
    public static void binaryInsertSort(int[] data) {
        int len = data.length;
        for (int i = 1; i < len; i++) {
            int tmp = data[i];
            int low = 0;
            int high = i - 1;
            while(low <= high) {
                int mid = (low + high) / 2;
                if (tmp > data[mid]) {
                    low = mid + 1;
                }
                else {
                    high = mid -1;
                }

            }for (int j = i;j > low ; j-- ) {
                data[j] = data[j - 1 ];
            }
            data[low] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] data = {5,2,7,3,9};
        binaryInsertSort(data);
        for (int d : data) {
            System.out.print(" " + d);
        }
    }
}

/**
 * Created by guo on 2018/2/2.
 * 二分查找法(折半查找)：前提是在已經排好序的數組中，通過將待查找的元素
 * 與中間索引值對應的元素進行比較，若大于中間索引值對應的元素，去右半邊查找，
 * 否則，去左邊查找。依次類推。直到找到位置；找不到返回一個負數
 */
public class BinarySearchSort {
    public static void main(String[] args) {
        //必須保證數列是有序的
        int[] nums = {12, 32, 55, 67, 87, 98};
        int i = binarySearch(nums, 87);
        System.out.println("查找數的下標為：" + i);   //輸出下標為4
    }

    /**
     * 二分查找算法
     *
     * @param nums
     * @param key
     * @return
     */
    public static int binarySearch(int[] nums, int key) {
        int start = 0;             //開始下標
        int end = nums.length - 1; //結束下標
        while (start <= end) {     //開始位置不能穿過結束位置 --start-->|<--end--
            int middle = (start + end) / 2;
            // 如果查找的key比中間的大，則去掉左邊的值
            if (key > nums[middle]) {
                start = middle + 1;
             //如果查找的key比中間的小，則去掉右邊的。
            } else if (key < nums[middle]) {
                end = middle - 1;             //結束位置需要向前移一位。
            } else {
                return middle;
            }
        }
        //找不到則返回-1
        return -1;
    }
}

先到這里吧，后續還得多敲幾遍，需要學習的太多了，gogogo。

給大家放兩個鏈接，GitHub、GitHub。里面收集的文章非常有水準，點進去不會失望的。

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/68683.html

相關文章

  • 排序算法

    摘要：排序代碼實現和一概念排序算法的穩定性穩定性穩定排序算法會讓原本有相等鍵值的紀錄維持相對次序。交換的結果導致結點的值變化了，重復，，的操作，直到沒有孩子時跳出代碼實現構建初始堆堆排序算法思想大頂堆舉例將待排序的序列構造成一個大頂堆。 排序 代碼實現：Java 和 Python 一、概念 1.1 排序算法的穩定性 穩定性：穩定排序算法會讓原本有相等鍵值的紀錄維持相對次序。也就是如果一個排序...

    kevin 評論0 收藏0

  • 排序算法

    摘要：排序代碼實現和一概念排序算法的穩定性穩定性穩定排序算法會讓原本有相等鍵值的紀錄維持相對次序。交換的結果導致結點的值變化了，重復，，的操作，直到沒有孩子時跳出代碼實現構建初始堆堆排序算法思想大頂堆舉例將待排序的序列構造成一個大頂堆。 排序 代碼實現：Java 和 Python 一、概念 1.1 排序算法的穩定性 穩定性：穩定排序算法會讓原本有相等鍵值的紀錄維持相對次序。也就是如果一個排序...

    binaryTree 評論0 收藏0

  • Python_數據結構與算法

    摘要：什么是數據結構數據的組織結構方式一組數據如何存儲，基本數據類型，，的封裝算法與數據結構的區別數據結構只是靜態的描述了數據元素之間的關系。高效的程序需要在數據結構的基礎上設計和選擇算法。 數據結構和算法基礎 什么是數據結構和算法：兵法，計算的方法。算法是獨立存在的一種解決問題的方法和思想。 算法的特征： 輸入：算法具有0個或多個輸入 輸出：算法至少有1個或多個輸出 有窮性：算法在有限的...

    Kylin_Mountain 評論0 收藏0

發表評論

0條評論

187J3X1

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<