直接插入排序java

⑴ java數組的插入排序

什麼狗蛋書,完全不知道在搞什麼.
要排序直接用API里的Arrays工具類就好.要學原理那都是數學的問題.代碼講究不要重復發明輪子.
排序這種大眾功能肯定已經有高手寫好了效率非常高的.完全沒有必要再去寫

⑵ Java排序一共有幾種

日常操作中，常見的排序方法有：冒泡排序、快速排序、選擇排序、插入排序、希爾排序，甚至還有基數排序、雞尾酒排序、桶排序、鴿巢排序、歸並排序等。

各類排序方法代碼如圖：

⑶ 請給出java幾種排序方法

java常見的排序分為：
1 插入類排序
主要就是對於一個已經有序的序列中，插入一個新的記錄。它包括：直接插入排序，折半插入排序和希爾排序
2 交換類排序
這類排序的核心就是每次比較都要「交換」，在每一趟排序都會兩兩發生一系列的「交換」排序，但是每一趟排序都會讓一個記錄排序到它的最終位置上。它包括：起泡排序，快速排序
3 選擇類排序
每一趟排序都從一系列數據中選擇一個最大或最小的記錄，將它放置到第一個或最後一個為位置交換，只有在選擇後才交換，比起交換類排序，減少了交換記錄的時間。屬於它的排序：簡單選擇排序，堆排序
4 歸並類排序
將兩個或兩個以上的有序序列合並成一個新的序列
5 基數排序
主要基於多個關鍵字排序的。
下面針對上面所述的演算法，講解一些常用的java代碼寫的演算法
二 插入類排序之直接插入排序
直接插入排序,一般對於已經有序的隊列排序效果好。
基本思想：每趟將一個待排序的關鍵字按照大小插入到已經排序好的位置上。
演算法思路，從後往前先找到要插入的位置，如果小於則就交換，將元素向後移動，將要插入數據插入該位置即可。時間復雜度為O(n2),空間復雜度為O(1)
package sort.algorithm;
public class DirectInsertSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int data[] = { 2, 6, 10, 3, 9, 80, 1, 16, 27, 20 };
int temp, j;
for (int i = 1; i < data.length; i++) {
temp = data[i];
j = i - 1;
// 每次比較都是對於已經有序的
while (j >= 0 && data[j] > temp) {
data[j + 1] = data[j];
j--;
}
data[j + 1] = temp;
}
// 輸出排序好的數據
for (int k = 0; k < data.length; k++) {
System.out.print(data[k] + " ");
}
}
}
三 插入類排序之折半插入排序(二分法排序)
條件：在一個已經有序的隊列中，插入一個新的元素
折半插入排序記錄的比較次數與初始序列無關
思想：折半插入就是首先將隊列中取最小位置low和最大位置high，然後算出中間位置mid
將中間位置mid與待插入的數據data進行比較，
如果mid大於data，則就表示插入的數據在mid的左邊，high=mid-1;
如果mid小於data，則就表示插入的數據在mid的右邊,low=mid+1
最後整體進行右移操作。
時間復雜度O(n2),空間復雜度O(1)

package sort.algorithm;
//折半插入排序
public class HalfInsertSort {
public static void main(String[] args) {
int data[] = { 2, 6, 10, 3, 9, 80, 1, 16, 27, 20 };
// 存放臨時要插入的元素數據
int temp;
int low, mid, high;
for (int i = 1; i < data.length; i++) {
temp = data[i];
// 在待插入排序的序號之前進行折半插入
low = 0;
high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (temp < data[mid])
high = mid - 1;
else
// low=high的時候也就是找到了要插入的位置，
// 此時進入循環中，將low加1，則就是要插入的位置了
low = mid + 1;
}
// 找到了要插入的位置，從該位置一直到插入數據的位置之間數據向後移動
for (int j = i; j >= low + 1; j--)
data[j] = data[j - 1];
// low已經代表了要插入的位置了
data[low] = temp;
}
for (int k = 0; k < data.length; k++) {
System.out.print(data[k] + " ");
}
}
}

四 插入類排序之希爾排序
希爾排序，也叫縮小增量排序，目的就是盡可能的減少交換次數，每一個組內最後都是有序的。
將待續按照某一種規則分為幾個子序列，不斷縮小規則，最後用一個直接插入排序合成
空間復雜度為O(1)，時間復雜度為O(nlog2n)
演算法先將要排序的一組數按某個增量d（n/2,n為要排序數的個數）分成若干組，每組中記錄的下標相差d.對每組中全部元素進行直接插入排序，然後再用一個較小的增量（d/2）對它進行分組，在每組中再進行直接插入排序。當增量減到1時，進行直接插入排序後，排序完成。

package sort.algorithm;
public class ShellSort {
public static void main(String[] args) {
int a[] = { 1, 54, 6, 3, 78, 34, 12, 45, 56, 100 };
double d1 = a.length;
int temp = 0;
while (true)
{
//利用這個在將組內倍數減小
//這里依次為5,3,2,1
d1 = Math.ceil(d1 / 2);
//d為增量每個分組之間索引的增量
int d = (int) d1;
//每個分組內部排序
for (int x = 0; x < d; x++)
{
//組內利用直接插入排序
for (int i = x + d; i < a.length; i += d) {
int j = i - d;
temp = a[i];
for (; j >= 0 && temp < a[j]; j -= d) {
a[j + d] = a[j];
}
a[j + d] = temp;
}
}

if (d == 1)
break;
}
for (int i = 0; i < a.length; i++)
System.out.print(a[i]+" ");
}
}

五 交換類排序之冒泡排序
交換類排序核心就是每次比較都要進行交換
冒泡排序：是一種交換排序
每一趟比較相鄰的元素，較若大小不同則就會發生交換，每一趟排序都能將一個元素放到它最終的位置！每一趟就進行比較。
時間復雜度O(n2)，空間復雜度O(1)

package sort.algorithm;
//冒泡排序：是一種交換排序
public class BubbleSort {
// 按照遞增順序排序
public static void main(String[] args) {
// TODO Auto-generated method stub
int data[] = { 2, 6, 10, 3, 9, 80, 1, 16, 27, 20, 13, 100, 37, 16 };
int temp = 0;
// 排序的比較趟數,每一趟都會將剩餘最大數放在最後面
for (int i = 0; i < data.length - 1; i++) {
// 每一趟從開始進行比較，將該元素與其餘的元素進行比較
for (int j = 0; j < data.length - 1; j++) {
if (data[j] > data[j + 1]) {
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
}
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
}
}

⑷ java基礎 insert方法問題

20大進階架構專題每日送達

1.直接插入排序

經常碰到這樣一類排序問題：把新的數據插入到已經排好的數據列中。

• 將第一個數和第二個數排序，然後構成一個有序序列

• 將第三個數插入進去，構成一個新的有序序列。

• 對第四個數、第五個數……直到最後一個數，重復第二步。

如何寫成代碼：


• 首先設定插入次數，即循環次數，for(int i=1;i

• 設定插入數和得到已經排好序列的最後一個數的位數。insertNum和j=i-1。

• 從最後一個數開始向前循環，如果插入數小於當前數，就將當前數向後移動一位。

• 將當前數放置到空著的位置，即j+1。

代碼實現如下：

public void insertSort(int[] a){
int length=a.length;//數組長度，將這個提取出來是為了提高速度。
int insertNum;//要插入的數
for(int i=1;i//插入的次數
insertNum=a[i];//要插入的數
int j=i-1;//已經排序好的序列元素個數
while(j>=0&&a[j]>insertNum){//序列從後到前循環，將大於insertNum的數向後移動一格
a[j+1]=a[j];//元素移動一格
j--;
}
a[j+1]=insertNum;//將需要插入的數放在要插入的位置。
}
}


2.希爾排序

• 對於直接插入排序問題，數據量巨大時。

• 將數的個數設為n，取奇數k=n/2，將下標差值為k的數分為一組，構成有序序列。

• 再取k=k/2 ，將下標差值為k的書分為一組，構成有序序列。

• 重復第二步，直到k=1執行簡單插入排序。

如何寫成代碼：

• 首先確定分的組數。

• 然後對組中元素進行插入排序。

• 然後將length/2，重復1,2步，直到length=0為止。

代碼實現如下：

public void sheelSort(int[] a){
int d = a.length;
while (d!=0) {
d=d/2;
for (int x = 0; x < d; x++) {//分的組數
for (int i = x + d; i < a.length; i += d) {//組中的元素，從第二個數開始
int j = i - d;//j為有序序列最後一位的位數
int temp = a[i];//要插入的元素
for (; j >= 0 && temp < a[j]; j -= d) {//從後往前遍歷。
a[j + d] = a[j];//向後移動d位
}
a[j + d] = temp;
}
}
}
}


3.簡單選擇排序

• 常用於取序列中最大最小的幾個數時。

(如果每次比較都交換，那麼就是交換排序；如果每次比較完一個循環再交換，就是簡單選擇排序。)

• 遍歷整個序列，將最小的數放在最前面。

• 遍歷剩下的序列，將最小的數放在最前面。

• 重復第二步，直到只剩下一個數。

如何寫成代碼：


• 首先確定循環次數，並且記住當前數字和當前位置。

• 將當前位置後面所有的數與當前數字進行對比，小數賦值給key，並記住小數的位置。

• 比對完成後，將最小的值與第一個數的值交換。

• 重復2、3步。

代碼實現如下：

public void selectSort(int[] a) {
int length = a.length;
for (int i = 0; i < length; i++) {//循環次數
int key = a[i];
int position=i;
for (int j = i + 1; j < length; j++) {//選出最小的值和位置
if (a[j] < key) {
key = a[j];
position = j;
}
}
a[position]=a[i];//交換位置
a[i]=key;
}
}


4.堆排序

• 對簡單選擇排序的優化。

• 將序列構建成大頂堆。

• 將根節點與最後一個節點交換，然後斷開最後一個節點。

• 重復第一、二步，直到所有節點斷開。

代碼實現如下：


public void heapSort(int[] a){
System.out.println("開始排序");
int arrayLength=a.length;
//循環建堆
for(int i=0;i-1;i++){
//建堆

buildMaxHeap(a,arrayLength-1-i);
//交換堆頂和最後一個元素
swap(a,0,arrayLength-1-i);
System.out.println(Arrays.toString(a));
}
}
private void swap(int[] data, int i, int j) {
// TODO Auto-generated method stub
int tmp=data[i];
data[i]=data[j];
data[j]=tmp;
}
//對data數組從0到lastIndex建大頂堆
private void buildMaxHeap(int[] data, int lastIndex) {
// TODO Auto-generated method stub
//從lastIndex處節點（最後一個節點）的父節點開始
for(int i=(lastIndex-1)/2;i>=0;i--){
//k保存正在判斷的節點
int k=i;
//如果當前k節點的子節點存在
while(k*2+1<=lastIndex){
//k節點的左子節點的索引
int biggerIndex=2*k+1;
//如果biggerIndex小於lastIndex，即biggerIndex+1代表的k節點的右子節點存在
if(biggerIndex //若果右子節點的值較大
if(data[biggerIndex]1]){
//biggerIndex總是記錄較大子節點的索引
biggerIndex++;
}
}
//如果k節點的值小於其較大的子節點的值
if(data[k] //交換他們
swap(data,k,biggerIndex);
//將biggerIndex賦予k，開始while循環的下一次循環，重新保證k節點的值大於其左右子節點的值
k=biggerIndex;
}else{
break;
}
}
}
}


5.冒泡排序

• 一般不用。

• 將序列中所有元素兩兩比較，將最大的放在最後面。

• 將剩餘序列中所有元素兩兩比較，將最大的放在最後面。

• 重復第二步，直到只剩下一個數。

如何寫成代碼：


• 設置循環次數。

• 設置開始比較的位數，和結束的位數。

• 兩兩比較，將最小的放到前面去。

• 重復2、3步，直到循環次數完畢。

代碼實現如下：

public void bubbleSort(int[] a){
int length=a.length;
int temp;
for(int i=0;i for(int j=0;j-1;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}


6.快速排序

• 要求時間最快時。

• 選擇第一個數為p，小於p的數放在左邊，大於p的數放在右邊。

• 遞歸的將p左邊和右邊的數都按照第一步進行，直到不能遞歸。

代碼實現如下：


public static void quickSort(int[] numbers, int start, int end) {
if (start < end) {
int base = numbers[start]; // 選定的基準值（第一個數值作為基準值）
int temp; // 記錄臨時中間值
int i = start, j = end;
do {
while ((numbers[i] < base) && (i < end))
i++;
while ((numbers[j] > base) && (j > start))
j--;
if (i <= j) {
temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
i++;
j--;
}
} while (i <= j);
if (start < j)
quickSort(numbers, start, j);
if (end > i)
quickSort(numbers, i, end);
}
}


7.歸並排序

• 速度僅次於快排，內存少的時候使用，可以進行並行計算的時候使用。

• 選擇相鄰兩個數組成一個有序序列。

• 選擇相鄰的兩個有序序列組成一個有序序列。

• 重復第二步，直到全部組成一個有序序列。

代碼實現如下：


public static void mergeSort(int[] numbers, int left, int right) {
int t = 1;// 每組元素個數
int size = right - left + 1;
while (t < size) {
int s = t;// 本次循環每組元素個數
t = 2 * s;
int i = left;
while (i + (t - 1) < size) {
merge(numbers, i, i + (s - 1), i + (t - 1));
i += t;
}
if (i + (s - 1) < right)
merge(numbers, i, i + (s - 1), right);
}
}
private static void merge(int[] data, int p, int q, int r) {
int[] B = new int[data.length];
int s = p;
int t = q + 1;
int k = p;
while (s <= q && t <= r) {
if (data[s] <= data[t]) {
B[k] = data[s];
s++;
} else {
B[k] = data[t];
t++;
}
k++;
}
if (s == q + 1)
B[k++] = data[t++];
else
B[k++] = data[s++];
for (int i = p; i <= r; i++)
data[i] = B[i];
}


8.基數排序

• 用於大量數，很長的數進行排序時。

• 將所有的數的個位數取出，按照個位數進行排序，構成一個序列。

• 將新構成的所有的數的十位數取出，按照十位數進行排序，構成一個序列。

代碼實現如下：


public void sort(int[] array) {
//首先確定排序的趟數;
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
int time = 0;
//判斷位數;
while (max > 0) {
max /= 10;
time++;
}
//建立10個隊列;
List queue = new ArrayList ();
for ( int i = 0; i < 10; i++) {
ArrayList queue1 = new ArrayList ();
queue.add(queue1);
}
//進行time次分配和收集;
for ( int i = 0; i < time; i++) {
//分配數組元素;
for ( int j = 0; j < array.length; j++) {
//得到數字的第time+1位數;
int x = array[j] % ( int) Math. pow( 10, i + 1) / ( int) Math. pow( 10, i);
ArrayList queue2 = queue.get(x);
queue2.add( array[j]);
queue. set(x, queue2);
}
int count = 0; //元素計數器;
//收集隊列元素;
for ( int k = 0; k < 10; k++) {
while ( queue.get(k).size() > 0) {
ArrayList queue3 = queue.get(k);
array[count] = queue3.get( 0);
queue3.remove( 0);
count++;
}
}
}
}

來源：KaelQ

地址：www.jianshu.com/p/5e171281a387

獲取方式：點「在看」，V信關注師長的小號：編程最前線並回復面試領取，更多精彩陸續奉上。

⑸ java編程題,對一組{23,55,-65,89,82,99,128}中的元素從小到大進行排序

• 1. 插入排序：插入排序基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，演算法適用於少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。插入排序的基本思想是：每步將一個待排序的紀錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。

• 2. 選擇排序：選擇排序（Selection sort）是一種簡單直觀的排序演算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。 選擇排序是不穩定的排序方法。

• 3. 冒泡排序：冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序演算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越大的元素會經由交換慢慢「浮」到數列的頂端。

• 4. 快速排序：快速排序（Quicksort）是對冒泡排序的一種改進。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

• 5. 歸並排序：歸並排序是建立在歸並操作上的一種有效的排序演算法,該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為二路歸並。

• 6. 希爾排序：希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法。希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法便終止。

你看這個鏈接，網頁鏈接

希望可以幫到你，望採納~