插入排序

[Ir1d]

https://oi-wiki.org/basic/insertion-sort/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[dddkl]

如果像冒泡排序那一样给出示例代码就好了

[GreyTigerOIer]

@dddkl
如果像冒泡排序那一样给出示例代码就好了

我交了，还没有审核完？

[Enter-tainer]

@MrFoodinChina 请问您发 pull request 了吗，只有发 pull request 管理才能看到你的修改，并合入主线

[GreyTigerOIer]

@Enter-tainer
@MrFoodinChina 请问您发 pull request 了吗，只有发 pull request 管理才能看到你的修改，并合入主线

F**k，我TMD的没交！谢谢提醒，已经交上去了

[thy233]

示例代码有误

[Enter-tainer]

@ToHolyForYou 您好，如果你认为代码出现错误，可以开一个issue指出问题，或者开一个pull request 来修正错误的部分

[Christmaso-0]

实例代码有问题，给一个能用的

void InsertSort(int a[], int n)
{
    for(int i= 1; i<n; i++){
        if(a[i] < a[i-1]){//若第 i 个元素大于 i-1 元素则直接插入；反之，需要找到适当的插入位置后在插入。
            int j= i-1;
            int x = a[i];
            while(j>-1 && x < a[j]){  //采用顺序查找方式找到插入的位置，在查找的同时，将数组中的元素进行后移操作，给插入元素腾出空间
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = x;      //插入到正确位置
        }
    }
}

[PlanariaIce]

实际上可以先用二分找到要插入的位置，再进行插入，虽然复杂度与示例代码相同，但减少了许多比较，常数会更小。

[JLibyvali]

二分的前提不是序列已经有序了吗？

[digua2010]

对于已经排好序的序列肯定有序啊

[qwq2519]

template<typename Iterator>
void InsertionSort(Iterator begin, Iterator end) {
    if (begin == end) return;
    for(auto it=begin;it!=end;++it){
        std::rotate(std::upper_bound(begin,it,*it),it,std::next(it));//upper_bound在[begin,it)二分查找第一个大于*it
    }

这个写法好像飞块。。

[16637851654]

为什么没有Java的示例代码呢

[zhangjialin996]

java插入排序：

class Solution {
    // 插入排序
    public int[] sortArray(int[] nums) {
        for(int i = 1; i < nums.length; i++){
            for(int j = i; j > 0; j--){
                if(nums[j] < nums[j - 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = temp;
                }
            }
        }
        return nums;
    }
}

二分查找优化：注意，找到从右向左第一个小于等于【！！！确保稳定性】当前值的位置。

class Solution {
    // 插入排序
    public int[] sortArray(int[] nums) {
        for(int i = 1; i < nums.length; i++){
            int left = 0, right = i - 1;
            // binary search
            while(left <= right){
                int mid = left + ((right - left) >> 1);
                if(nums[mid] > nums[i]){
                    right = mid - 1;
                }else {
                    left = mid + 1;
                }
            }
            int temp = nums[i];
            // 移动
            for(int j = i; j > left; j--){
                nums[j] = nums[j - 1];
            }
            nums[left] = temp;
        }
        return nums;
    }
}

复杂度为什么不变？
当你找到一个插入位置，你需要将插入位置之后的所有元素后移一个单位【O(n)】，再将新元素插入中间位置。【相比优化之前，减少了比较的开销，因为优化之前每次移动都要进行比较，优化后只需要比较logn次】

[zhangjialin996]

leetcode912自行验证，超时属于正常现象

[zhzbubai]

这是我用while()循环写的,请点评：
void Sort::InsertSort()
{
int count = 1;
while(count != cmaxn){
int i = count;
int temp = 0;
while(i != 0){
if(carray[i] < carray[i - 1]){
temp = carray[i - 1];
carray[i - 1] = carray[i];
carray[i] = temp;
}
i--;
}
count++;
}
}