# 概述
---
##### 排序有內部排序和外部排序,內部排序是數據記錄在內存中進行排序,而外部排序是因排序的數據很大,一次不能容納全部的排序記錄,在排序過程中需要訪問外存。
##### 我們這里說說八大排序就是內部排序。

當n較大,則應采用時間復雜度為O(nlog2n)的排序方法:快速排序、堆排序或歸并排序序。
快速排序:是目前基于比較的內部排序中被認為是最好的方法,當待排序的關鍵字是隨機分布時,快速排序的平均時間最短;
## 1.插入排序—直接插入排序(Straight Insertion Sort)
### 基本思想:
將一個記錄插入到已排序好的有序表中,從而得到一個新,記錄數增1的有序表。即:先將序列的第1個記錄看成是一個有序的子序列,然后從第2個記錄逐個進行插入,直至整個序列有序為止。
要點:設立哨兵,作為臨時存儲和判斷數組邊界之用。
直接插入排序示例:

如果碰見一個和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后順序沒有改變,從原無序序列出去的順序就是排好序后的順序,所以插入排序是穩定的。
### 算法的實現:
package com;
public class InsertSort {
public static void main(String[] args) {
int a[] = {3,1,5,7,2,4,9,6,10,8};
InsertSort obj=new InsertSort();
System.out.println("初始值:");
obj.print(a);
obj.insertSort(a);
System.out.println("\n排序后:");
obj.print(a);
}
public void print(int a[]){
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
public void insertSort(int[] a) {
for(int i=1;i<a.length;i++){//從頭部第一個當做已經排好序的,把后面的一個一個的插到已經排好的列表中去。
if(a[i]<a[i-1]){
int j;
int x=a[i];//x為待插入元素
a[i]=a[i-1];
for(j=i-1; j>=0 && x<a[j];j--){//通過循環,逐個后移一位找到要插入的位置。
a[j+1]=a[j];
} ``
a[j+1]=x;//插入
}
}
}
}
- 說明
- 《Java 基礎》
- 第01章 Java 概述
- 第02章 Java 語言語法
- 第03章 Java 面向對象編程
- 第04章 Java 常見API
- 第05章 Java 集合框架
- 第06章 Java 多線程和并發
- 第07章 Java I\O流
- 第08章 Java 網絡編程
- 第09章 Java 數據結構
- 第10章 Java 設計模式
- 《Android 基礎》
- 第00章 Android Studio 中的項目結構
- 第01章 AndroidManifest
- 第02章 UI
- 第03章 Activity
- 第04章 Service
- 第05章 BroadcastReceiver
- 第06章 ContentProvider
- 第07章 Intent
- 第08章 多線程
- 《數據庫基礎》
- 第01章 SQL 語句基礎
- 第02章 SQLite 基礎
- 《數據結構》
- chapter 1
- 《算法》
- chapter 1
- 《網絡基礎》
- 面試常見網絡知識解答
- 1.1.網絡協議簡介
- 1.2.
- 1.3.
- 1.4.
- 1.5.
- 《項目經驗》
- 序言
- 公司項目
- 開源項目
- 自有項目
- 《回首與展望》
- 《開始的地方》
- 1.初識計算機
- 2.時刻準備著
- 《在路上》
- 1.最寒冷的冬天
- 2.做了一回鳥人
- 3.5月出租屋
- 4.魔都
- 5.回長安
- 6.煉獄
- 7.最后的路
- 《遇到的坑》
- 《正在做的事》
- 《未來》
- 附錄 1:10大基礎算法
- 1.快速排序算法
- 2.堆排序算法
- 3.歸并排序
- 4.二分查找算法
- 5.BFPRT(線性查找算法)
- 6.DFS(深度優先搜索)
- 7.BFS(廣度優先搜索)
- 8.Dijkstra算法
- 9.動態規劃算法
- 10.樸素貝葉斯分類算法
- 附錄 2:面試常考算法
- 第1章 常考排序算法
- 1.1.冒泡排序
- 1.2.快速排序
- 第2章 常考搜索算法
- 2.1.二分查找
- 附錄 3:Java八大排序算法
- 最后的話