插入排序  


難度級別 中烘焙
經常問 埃森哲 思科 戴爾 雜貨店 瞻博網絡 空氣質量 法國國際檢驗
排列 排序

使用插入排序算法對給定的未排序數組進行排序。

輸入: 9,5,1,6,11,8,4 {}

輸出: 1,4,5,6,8,9,11 {}

理論  

  • 插入排序對數字進行排序的方式與人類對一組編號對象(例如卡片)進行排序的方式相同
  • 從未排序的數組(右側的子數組)到已排序的數組(左側的子數組)中的某個位置取一個數字,以使左側的子數組保持排序。
  • 這是一種基於增量方法的方法。

插入排序算法  

  1. 選擇/標記未排序數組中的第一個元素,將其移動到已排序數組中的正確位置。
  2. 將標記前進到未排序數組中的下一個元素。

插入排序

C ++程序  

#include <iostream>
using namespace std;

void insertSort(int arr[],int n)
{
    int i,j,save;

    for(int i=1;i<n;i++)
    {
        j = i-1;
        save = arr[i];
        
        // look for correct position of arr[i]
        while(j>=0 && arr[j] > save)
        {
            // shifting array elements towards the right
            arr[j+1] = arr[j];
            j--;
        }
        // place arr[i] at the correct position
        arr[j+1] = save;
    }
}

int main()
{
    
    int arr[] = {9,5,1,6,11,8,4};
    int n = sizeof(arr)/sizeof(arr[0]);

    insertSort(arr,n);

    for(int i=0;i<n;i++)
    cout<<arr[i]<<" ";
    
    return 0;
}

產量

1 4 5 6 8 9 11

Java程序  

class iSort
{
    static void insertSort(int arr[])
    {
        int n = arr.length;
        int i,j,save;

        for(i=1;i<n;i++)
        {
            j = i-1;
            save = arr[i];

            // look for correct position of arr[i]
            while(j >= 0 && arr[j] > save)
            {
                // shifting array elements towards the right
                arr[j+1] = arr[j];
                j--;
            }
            // place arr[i] at the correct position
            arr[j+1] = save;
        }
    }

    public static void main(String args[]) 
    {
        int arr[] = {9,5,1,6,11,8,4};
        insertSort(arr);

        for(int i=0;i<arr.length;i++)
        System.out.print(arr[i] +" ");   
    }
}

產量

1 4 5 6 8 9 11

複雜度分析  

  • 時間複雜度: T(n)= O(n2)
  • 花費O(n2)對數組進行反向排序的時間,以及O(n)對數組進行排序的時間。
  • 空間複雜度: A(n)= O(1)
也可以看看
兩個給定數組中的最大數組保持順序相同

補充資料  

  • 插入排序是一種就地排序算法。
  • 這是穩定的性質。
  • 當輸入數組幾乎排序時,只有少數幾個元素被放置在不完整的大數組中,因此插入排序很有用。
  • 當要排序的數組的大小較小時,它也很有用。

參考文獻  面試問題