插入排序 Insert sort

港控/mmm° 2021-12-20 15:03 260阅读 0赞

//直接插入排序
    void DirectInsertionSort(int* arr, int nLen)
    {
        int i, j;
        for (i=1; i<nLen; i++)
        {
            int temp = arr[i];
            for (j=i-1; j>=0; j--)
            {
                if (temp < arr[j])
                    arr[j+1] = arr[j];
                else
                    break;
            }
            if (j+1 != i)
                arr[j+1] = temp;    //注意这里是j+1
        }
    }
    
    //折半插入排序
    void BinaryInsertionSort(int* arr, int nLen)
    {
        int i, j;
        int low, mid, high;
        for (i=1; i<nLen; i++)
        {
            int temp = arr[i];
            if (temp < arr[i-1])//这个判断可不要
            {
                low = 0;
                high = i-1;
                while (low <= high) //error: while( low < high) 注意这里还需要 等号
                {
                    mid = (low+high)/2;
                    if (temp < arr[mid]) 
                        high = mid - 1;
                    else 
                        low = mid + 1;
                }
                //经过上面的折半查找插入位置后，这时插入位置为low或者high+1,这时low等于high+1
                //for (j=i-1; j>=high+1; j--)
                //{
                //    arr[j+1] = arr[j];
                //}
                //arr[high+1] = temp; 
    
                for (j=i-1; j>=low; j--) 
                {
                    arr[j+1] = arr[j];
                }
                arr[low] = temp; 
            }
        }
    }

转载于:https://www.cnblogs.com/RicoRico/archive/2013/03/02/2941107.html

发表评论取消回复

表情：

评论列表（有 0 条评论，260人围观）

还没有评论，来说两句吧...

相关阅读

相关 java sort 插入排序_java插入排序 Insert sort实例

//直接插入排序 void directinsertionsort(int\ arr, int nlen) \{ int i, j; for (i=1; i \{

川长思鸟来/ 2022年11月12日 02:41/ 0 赞/ 195 阅读

相关 leetcode 147. Insertion Sort List 链表插入排序

Sort a linked list using insertion sort. 本题就是要做链表的插入排序。代码如下： /class ListNode

矫情吗；*/ 2022年06月08日 04:58/ 0 赞/ 183 阅读

相关插入排序（Insertion Sort）

一，插入排序算法分析插入排序算法有种递归的思想在里面，它由N-1趟排序组成。初始时，只考虑数组下标0处的元素，只有一个元素，显然是有序的。然后第一趟对下标 1 处的元

谁践踏了优雅/ 2022年05月26日 09:42/ 0 赞/ 120 阅读

相关 5. insertion-sort-list 链表插入排序

题目描述 Sort a linked list using insertion sort. 对一个链表进行插入排序题目解析上一道题对链表进行归并排序和冒泡排

阳光穿透心脏的1/2处/ 2022年05月23日 11:24/ 0 赞/ 134 阅读

相关图解排序算法及实现——插入排序（Insertion Sort）

插入排序（InsertionSort）可以说是最简单直观的排序算法了。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。通常以

蔚落/ 2022年05月14日 05:16/ 0 赞/ 219 阅读

相关 (PAT)Insertion or Heap Sort(堆排序与插入排序)

Insertion sort iterates, consuming one input element each repetition, and growing a sort

小咪咪/ 2022年04月18日 06:10/ 0 赞/ 179 阅读

相关 4.图解-折半插入排序 Binary insert sort

1. 思想 > 折半插入排序是对直接插入排序的改进。直接插入排序就是不断的依次将元素插入前面已经排好序的序列中。 > 由于前半部分为已经排好的序列，这样就不

逃离我推掉我的手/ 2022年04月13日 13:13/ 0 赞/ 151 阅读

相关插入排序 Insert sort

//直接插入排序 void DirectInsertionSort(int arr, int nLen) { int i, j;

港控/mmm°/ 2021年12月20日 15:03/ 0 赞/ 261 阅读

相关 1098 Insertion or Heap Sort (25 分) 插入排序or堆排序

1098 Insertion or Heap Sort (25 分) According to Wikipedia: Insertion sort iterates, co

快来打我*/ 2021年10月30日 05:44/ 0 赞/ 258 阅读

相关 Java 插入排序（Insertion Sort）

文章目录 * 算法描述动图演示代码实现算法分析插入排序（Insertion-Sort）的算法描述是...

你的名字/ 2020年06月14日 02:27/ 0 赞/ 737 阅读