程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 排序算法(二) 插入排序

排序算法(二) 插入排序

編輯:關於C語言

插入排序:

從頭到尾遍歷數組

將當前元素同當前元素之前的所有元素對比
如果,當前元素小於其之前元素,將當前元素向前移,直到使當前元素之前的所有元素按大小排好序

代碼如下:

[html] 
package com.robert.paixu; 
 
/** 
 * 插入排序 
 * 從小到大排序 
 * @author Administrator 
 */ 
public class InsertSortAlgorithm { 
     
    public static void main(String[] args){ 
        int[] arrays = {4,6,9,2,0,1,-5,10,-20,100,20,15}; 
        insertSort(arrays); 
        display(arrays); 
    } 
     
    /** 
     * 插入排序 
     */ 
    private static void insertSort(int[] arrays){ 
        //循環遍歷數組 
        int currentIndex = 0; 
        int preIndex = 0; 
        for(int i=0;i<arrays.length;i++) 
        { 
            /** 
             * 當前元素同當前元素之前的所有元素對比 
             * 1,將當前元素向前移,直到使當前元素之前的所有元素按大小排好序 
             */ 
            currentIndex = i; 
            preIndex = i-1; 
            while(currentIndex!=0&&preIndex>=0){ 
                if(arrays[currentIndex]<arrays[preIndex]) 
                { 
                    swap(arrays,currentIndex,preIndex); 
                    currentIndex--; 
                } 
                else 
                { 
                    break; 
                } 
                preIndex--; 
            } 
        } 
    } 
     
    private static void swap(int[] arrays,int currentIndex,int preIndex){ 
        int temp = arrays[currentIndex]; 
        arrays[currentIndex] = arrays[preIndex]; 
        arrays[preIndex] = temp; 
    } 
     
    /** 
     * 顯示排序後的數組的值 
     * @param arrays 
     */ 
    private static void display(int[] arrays){ 
         
        for(int i=0;i<arrays.length;i++){ 
            System.out.print(arrays[i]+" "); 
        } 
    } 
     

在最好的情況下,即數組已經是有序的時候,插入排序的時間復雜度是O(n)

數組越有序,需要做的工作就越少

在最壞的情況下,該算法在最壞的情況下的時間復雜度為O(n^2)
 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved