Direct Insertion

本文主要是介绍Direct Insertion，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

直接插入排序是稳定的排序，时间复杂度为O(n^2)

#include<iostream>
using namespace std;void sorting(int arr[],int n)
{for(int i = 1;i < n;i++){if(arr[i] >= arr[i-1])continue;int current = arr[i];int j;for(j = i-1;j >= 0;j--){if(current >= arr[j])break;}for(int k = i-1;k >= j+1;k--)arr[k+1] = arr[k];arr[j+1] = current;}
}int main()
{int arr[] = {8,7,2,9,4,2,1,0,10,-2,6};int n = sizeof(arr) / sizeof(arr[0]);sorting(arr, n);for(int i = 0;i < n;i++)cout<<arr[i]<<" ";cout<<endl;return 0;
}

更简单的更优化的代码是，边比较边移动，这就不用搞错插入位置了。

<pre name="code" class="cpp">#include<iostream>
using namespace std;void sorting(int arr[],int n)
{for(int i = 1;i < n;i++){int j = i;while(j>0 && arr[j]<arr[j-1]){int temp = arr[j];arr[j] = arr[j-1];arr[j-1] = temp;j--;}}
}int main()
{int arr[] = {8,7,2,9,4,2,1,0,10,-2,6};int n = sizeof(arr) /sizeof(arr[0]);sorting(arr, n);for(int i = 0;i < n;i++)cout<<arr[i]<<" ";cout<<endl;return 0;

这篇关于Direct Insertion的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---