插入排序 订阅
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 [1]  。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 [2]  。 展开全文
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 [1]  。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 [2]  。
信息
外文名
Insertion sort
空间复杂度
O(1)
别    称
直接插入排序
分    类
排序方法
中文名
插入排序
时间复杂度
O(N^(1-2))
稳定性
稳定
插入排序基本思想
插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌 [1]  。插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序 [3]  。
收起全文
精华内容
下载资源
问答
我要提问

  • 插入排序

     2021-01-20 03:30:30
    根据寻找插入位置的不同方式，可将插入排序分为直接插入排序和折半插入排序，还有一种对直接插入排序的优化方案希尔排序。 直接插入排序 直接插入排序的是，将一组待排序的元素第一个元素看做是有序的，然后从第二个... 
    
                                    
    
                                    
    收起 
    
                                
    
                            
    

                        
    • 
                        
  • 
                            
    
                                
                                    
    六大排序算法：插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序
    
                                    
                                    
                                            万次阅读
                                            多人点赞
                                    
                                2021-07-23 21:56:09
                            
    
                            
    
                                
    
                                     插入排序2.希尔排序  1. 插入排序 步骤： 1.从第一个元素开始，该元素可以认为已经被排序 2.取下一个元素tem，从已排序的元素序列从后往前扫描 3.如果该元素大于tem，则将该元素移到下一位 4.重复步骤3，直到找到已...
                                
    
                                
    
                                    
    
                                        
    

    
 
    文章目录：
    
 

    

     

     

    1. 插入排序
     

    步骤：
     

    1.从第一个元素开始，该元素可以认为已经被排序
     2.取下一个元素tem，从已排序的元素序列从后往前扫描
     3.如果该元素大于tem，则将该元素移到下一位
     4.重复步骤3，直到找到已排序元素中小于等于tem的元素
     5.tem插入到该元素的后面，如果已排序所有元素都大于tem，则将tem插入到下标为0的位置
     6.重复步骤2~5
     

    动图演示如下：在这里插入图片描述
     思路：
       在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。
       但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。
     在这里插入图片描述
     代码如下：
     

    void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; ++i)
	{
		//记录有序序列最后一个元素的下标
		int end = i;
		//待插入的元素
		int tem = arr[end + 1];
		//单趟排
		while (end >= 0)
		{
			//比插入的数大就向后移
			if (tem < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			//比插入的数小，跳出循环
			else
			{
				break;
			}
		}
		//tem放到比插入的数小的数的后面
		arr[end  + 1] = tem;
		//代码执行到此位置有两种情况:
		//1.待插入元素找到应插入位置（break跳出循环到此）
		//2.待插入元素比当前有序序列中的所有元素都小（while循环结束后到此）
	}
}

     

     
 
    时间复杂度：最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序
           最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
     空间复杂度：O(1)
     

     

    2.希尔排序
     

    步骤：
     1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…
     2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。
     动图如下：
     在这里插入图片描述
     思路：
     希尔排序，先将待排序列进行预排序，使待排序列接近有序，然后再对该序列进行一次插入排序，此时插入排序的时间复杂度为O(N)，
     

    代码如下：
     

    //希尔排序
void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap>1)
	{
		//每次对gap折半操作
		gap = gap / 2;
		//单趟排序
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tem = arr[end + gap];
			while (end >= 0)
			{
				if (tem < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tem;
		}
	}
}

     

     
 
    时间复杂度平均：O(N^1.3)
     空间复杂度：O(1)
     

     

    3.选择排序
     

    思路：
     每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。
     实际上，我们可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。
     

    动图如下：
     在这里插入图片描述
     代码如下：
     

    //选择排序
void swap(int* a, int* b)
{
	int tem = *a;
	*a = *b;
	*b = tem;
}
void SelectSort(int* arr, int n)
{
	//保存参与单趟排序的第一个数和最后一个数的下标
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		//保存最大值的下标
		int maxi = begin;
		//保存最小值的下标
		int mini = begin;
		//找出最大值和最小值的下标
		for (int i = begin; i <= end; ++i)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		//最小值放在序列开头
		swap(&arr[mini], &arr[begin]);
		//防止最大的数在begin位置被换走
		if (begin == maxi)
		{
			maxi = mini;
		}
		//最大值放在序列结尾
		swap(&arr[maxi], &arr[end]);
		++begin;
		--end;
	}
}

     

     
 
    时间复杂度：最坏情况：O(N^2)
           最好情况：O(N^2)
     空间复杂度：O(1)
     

     

    4.冒泡排序
     

    思路：
     左边大于右边交换一趟排下来最大的在右边
     

    动图如下：
     在这里插入图片描述
     代码如下：
     

    //冒泡排序
void BubbleSort(int* arr, int n)
{
	int end = n;
	while (end)
	{
		int flag = 0;
		for (int i = 1; i < end; ++i)
		{
			if (arr[i - 1] > arr[i])
			{
				int tem = arr[i];
				arr[i] = arr[i - 1];
				arr[i - 1] = tem;
				flag = 1;
			}
		}
		if (flag == 0)
		{
			break;
		}
		--end;
	}
}

     

     
 
    时间复杂度：最坏情况：O(N^2)
           最好情况：O(N)
     空间复杂度：O(1)
     

     

    5.堆排序
     

    堆排可看之间这篇博文----->[堆排]
     

    6.快速排序
     

    5.1 hoare版本(左右指针法)
     

    思路：
     1、选出一个key，一般是最左边或是最右边的。
     2、定义一个begin和一个end，begin从左向右走，end从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要end先走；若选择最右边的数据作为key，则需要bengin先走）。
     3、在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到begin遇到一个大于key的数时，将begin和right的内容交换，end再次开始走，如此进行下去，直到begin和end最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）
     4.此时key的左边都是小于key的数，key的右边都是大于key的数
     5.将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时此部分已有序
     

    单趟动图如下：
     在这里插入图片描述
     代码如下：
     

    //快速排序   hoare版本(左右指针法)
void QuickSort(int* arr, int begin, int end)
{
	//只有一个数或区间不存在
	if (begin >= end)
		return;
	int left = begin;
	int right = end;
	//选左边为key
	int keyi = begin;
	while (begin < end)
	{
		//右边选小   等号防止和key值相等    防止顺序begin和end越界
		while (arr[end] >= arr[keyi] && begin < end)
		{
			--end;
		}
		//左边选大
		while (arr[begin] <= arr[keyi] && begin < end)
		{
			++begin;
		}
		//小的换到右边，大的换到左边
		swap(&arr[begin], &arr[end]);
	}
	swap(&arr[keyi], &arr[end]);
	keyi = end;
	//[left,keyi-1]keyi[keyi+1,right]
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr,keyi + 1,right);
}

     

     
 
    时间复杂度:
     在这里插入图片描述
     快速排序的过程类似于二叉树其高度为logN，每层约有N个数，如下图所示：在这里插入图片描述
     

     

    5.2 挖坑法
     

    5.2.1 递归
     

    思路：
     挖坑法思路与hoare版本(左右指针法)思路类似
     1.选出一个数据（一般是最左边或是最右边的）存放在key变量中，在该数据位置形成一个坑
     2、还是定义一个L和一个R，L从左向右走，R从右向左走。（若在最左边挖坑，则需要R先走；若在最右边挖坑，则需要L先走）
     

    后面的思路与hoare版本(左右指针法)思路类似在此处就不说了
     

    单趟动图如下：
     在这里插入图片描述
     代码如下：
     

    //快速排序法  挖坑法
void QuickSort1(int* arr, int begin, int end)
{
	if (begin >= end)
		return;
	int left = begin,right = end;
	int key = arr[begin];
	while (begin < end)
	{
		//找小
		while (arr[end] >= key && begin < end)
		{
			--end;
		}
		//小的放到左边的坑里
		arr[begin] = arr[end];
		//找大
		while (arr[begin] <= key && begin < end)
		{
			++begin;
		}
		//大的放到右边的坑里
		arr[end] = arr[begin];
	}
	arr[begin] = key;
	int keyi = begin;
	//[left,keyi-1]keyi[keyi+1,right]
	QuickSort1(arr, left, keyi - 1);
	QuickSort1(arr, keyi + 1, right);
}

     

    5.2.2 非递归
     

    //单趟排
int PartSort(int* arr, int begin, int end)
{
	int key = arr[begin];
	while (begin < end)
	{
		while (key <= arr[end] && begin < end)
		{
			--end;
		}
		arr[begin] = arr[end];
		while (key >= arr[begin] && begin < end)
		{
			++begin;
		}
		arr[end] = arr[begin];
	}
	arr[begin] = key;
	int meeti = begin;
	return meeti;
}

void QuickSortNoR(int* arr, int begin, int end)
{
	stack<int> st;
	//先入右边
	st.push(end);
	//再入左边
	st.push(begin);
	while (!st.empty())
	{
		//左区间
		int left = st.top();
		st.pop();
		//右区间
		int right = st.top();
		st.pop();
		//中间数
		int mid = PartSort(arr, left, right);
		//当左区间>=mid-1则证明左区间已经排好序了
		if (left < mid - 1)
		{
			st.push(mid - 1);
			st.push(left);
		}
		//当mid+1>=右区间则证明右区间已经排好序
		if (right > mid + 1)
		{
			st.push(right);
			st.push(mid + 1);
		}
	}
}

     

    5.3 前后指针法
     

    思路：
     1、选出一个key，一般是最左边或是最右边的。
     2、起始时，prev指针指向序列开头，cur指针指向prev+1。
     3、若cur指向的内容小于key，则prev先向后移动一位，然后交换prev和cur指针指向的内容，然后cur指针++；若cur指向的内容大于key，则cur指针直接++。如此进行下去，直到cur到达end位置，此时将key和++prev指针指向的内容交换即可。
     

    经过一次单趟排序，最终也能使得key左边的数据全部都小于key，key右边的数据全部都大于key。
     

    然后也还是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作
     

    //快速排序法  前后指针版本
void QuickSort2(int* arr, int begin, int end)
{
	if (begin >= end)
		return;
	int cur = begin, prev = begin - 1;
	int keyi = end;
	while (cur != keyi)
	{
		if (arr[cur] < arr[keyi] && ++prev != cur)
		{
			swap(&arr[cur], &arr[prev]);
		}
		++cur;
	}
	swap(&arr[++prev],&arr[keyi]);
	keyi = prev;
	//[begin,keyi -1]keyi[keyi+1,end]
	QuickSort2(arr, begin, keyi - 1);
	QuickSort2(arr, keyi + 1, end);

}

    
                                    
    
                                    
    收起 
    
                                
    
                                        
                                            展开全文
                                            
                                        
                            
    
                                
    
                                    
                                        数据结构   
                                        快速排序   
                                        排序算法   
                                        堆排序   
                                
    

                        
    • 
                        
  • 
                            
    
                                
                                    
    算法 - 插入排序（C#）
    
                                    
                                    
                                            万次阅读
                                            多人点赞
                                    
                                2019-02-01 10:58:01
                            
    
                            
    
                                
    
                                     * 直接插入排序（straight insertion sort）的做法是：  * 每次从无序表中取出第一个元素，把它插入到有序表的合适位置使有序表仍然有序，直至无序表中所有元素插入完为止。  * 第一趟扫描前两个数，然后把第二个数...
                                
    
                                
    
                                    
    
                                        
    分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net 
     

    /*
 * 直接插入排序（straight insertion sort）的做法是：
 * 每次从无序表中取出第一个元素，把它插入到有序表的合适位置使有序表仍然有序，直至无序表中所有元素插入完为止。
 * 第一趟扫描前两个数，然后把第二个数按大小顺序插入到有序表中；
 * 第二趟把第三个数与前两个数从前向后扫描，把第三个数按大小插入到有序表中；
 * 依次进行下去，进行了（n-1）趟扫描以后就完成了整个排序过程。
 * 
 * 直接插入排序属于稳定的排序，最坏时间复杂度为O（n^2），空间复杂度为O（1）。
 * 
 * 直接插入排序是由两层嵌套循环组成的。
 * 外层循环标识并决定待比较的数值，内层循环为待比较数值确定其最终位置。
 * 直接插入排序是将待比较的数值与它的前一数值进行比较，所以外层循环是从第二个数值开始的。
 * 当前一数值比待比较数值大的情况下后移该数值并继续循环比较，
 * 直到找到比待比较数值小的并将待比较数值插入其后一位置，结束该次循环。
 * 值得注意的是，我们必需用一个存储空间来保存当前待比较的数值，
 * 因为当一趟比较完成时，我们要将待比较数值插入比它小的数值的后一位置。
 * 插入排序类似于玩纸牌时整理手中纸牌的过程。
*/

namespace InsertionSort
{
    using System;

    /// <summary>
    /// The program.
    /// </summary>
    public static class Program
    {
        /// <summary>
        /// The main.
        /// </summary>
        public static void Main()
        {
            int[] a = {1, 4, 6, 2, 8, 7, 9, 3, 5, 10};

            Console.WriteLine("Before Insertion Sort:");
            foreach (int i in a)
            {
                Console.Write(i + " ");
            }

            Console.WriteLine("\r\n\r\nIn Insertion Sort:");
            InsertionSort(a);

            Console.WriteLine("\r\nAfter Insertion Sort:");
            foreach (int i in a)
            {
                Console.Write(i + " ");
            }
        }

        /// <summary>
        /// The insertion sort.
        /// </summary>
        /// <param name="a">
        /// The a.
        /// </param>
        public static void InsertionSort(int[] a)
        {
            // 从第二个元素开始迭代。
            for (int i = 1; i < a.Length; i++)
            {
                // 存储待插入的元素。
                int tmp = a[i];
                int j = i - 1;

                // 从当前元素右边寻找插入点。
                while (a[j] > tmp)
                {
                    // 后移。
                    a[j + 1] = a[j];
                    j--;
                    if (j == -1)
                    {
                        break;
                    }
                }

                // 该后移的元素已经后移了，会留下一个空位置，这个位置就是待插入元素的插入点。
                a[j + 1] = tmp;

                // 打印数组。
                foreach (int k in a)
                {
                    Console.Write(k + " ");
                }

                Console.WriteLine(string.Empty);
            }
        }
    }
}

// Output:
/*
Before Insertion Sort:
1 4 6 2 8 7 9 3 5 10

In Insertion Sort:
1 4 6 2 8 7 9 3 5 10
1 4 6 2 8 7 9 3 5 10
1 2 4 6 8 7 9 3 5 10
1 2 4 6 8 7 9 3 5 10
1 2 4 6 7 8 9 3 5 10
1 2 4 6 7 8 9 3 5 10
1 2 3 4 6 7 8 9 5 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

After Insertion Sort:
1 2 3 4 5 6 7 8 9 10
*/
     

     
    
                                    
    
                                    
    收起 
    
                                
    
                                        
                                            展开全文
                                            
                                        
                            
    
                                
    
                                    
                                        算法   
                                        C#   
                                
    

                        
    • 
                        
  • 
                            
    
                                
                                    
    排序算法 插入排序（直接插入排序、半插入排序、希尔排序）
    
                                    
                                    
                                            万次阅读
                                            多人点赞
                                    
                                2019-10-19 14:46:31
                            
    
                            
    
                                
    
                                    一、直接插入排序。  1、介绍。   直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。...
                                
    
                                
    
                                    
    
                                        
    一、直接插入排序。
     

    1、介绍。
     

            直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。例如,已知待排序的一组记录是：60,71,49,11,24,3,66。假设在排序过程中，前3个记录已按关键码值递增的次序重新排列，构成一个有序序列：49,60,71。将待排序记录中的第4个记录（即11）插入上述有序序列，以得到一个新的含4个记录的有序序列。首先，应找到11的插入位置，再进行插入。可以将11放入数组的第一个单元r[0]中，这个单元称为监视哨，然后从71起从右到左查找，11小于71，将71右移一个位置，11小于60，又将60右移一个位置，11小于49，又再将49右移一个位置，这时再将11与r[0]的值比较，11≥r[0]，它的插入位置就是r[1]。假设11大于第一个值r[1]。它的插入位置应该在r[1]和r[2]之间，由于60已经右移了，留出来的位置正好留给11.后面的记录依照同样的方法逐个插入到该有序序列中。若记录数n,续进行n-1趟排序，才能完成。 
     

            直接插入排序是稳定排序，不需要额外内存，空间复杂度O(1)。时间复杂度，最佳情况：O(n)  最差情况：O(n^2)  平均情况：O(n^2)。
     

    2、步骤。
     

        (1)设置监视哨r[0]，将待插入记录的值赋值给r[0]；
         (2)设置开始查找的位置j；
         (3)在数组中进行搜索，搜索中将第j个记录后移，直至r[0].key≥r
    
                                    
    
                                    
    收起 
    
                                
    
                                        
                                            展开全文
                                            
                                        
                            
    
                                
    
                                    
                                        排序算法   
                                        希尔排序   
                                
    

                        
    • 
                        
  • 
                            
    
                                
                                    
    插入排序之直接插入排序.cpp
    
                                    
                                2019-08-03 22:23:19
                            
    
                            
    
                                
    
                                    插入排序之直接插入排序.cpp
                                
    
                                
    
                                    
    
                                        
    
                                    
    
                                    
    收起 
    
                                
    
                            
    

                        
    • 
                        
  • 
                            
    
                                
                                    
    浅析直接插入排序与折半插入排序
    
                                    
                                2020-09-04 19:19:25
                            
    
                            
    
                                
    
                                    主要介绍了直接插入排序与折半插入排序，有需要的朋友可以参考一下
                                
    
                                
    
                                    
    
                                        
    
                                    
    
                                    
    收起 
    
                                
    
                            
    

                        
    • 
                        
  • 
                            
    
                                
                                    
    C++实现插入排序算法（直接插入排序、折半插入排序、希尔排序）
    
                                    
                                    
                                            千次阅读
                                            多人点赞
                                    
                                2020-11-01 13:53:47
                            
    
                            
    
                                
    
                                    插入类：直接插入排序、折半插入排序、希尔排序 交换类：冒泡排序、快速排序 选择类：简单选择排序、堆排序 归并类：二路归并排序 基数类：多关键字排序 九种算法的时间复杂度、空间复杂度和稳定性小结如下：  本文...
                                
    
                                
    
                                    
    
                                        
    排序算法分为五大类，一共是有九种，如下：
     插入类：直接插入排序、折半插入排序、希尔排序
     交换类：冒泡排序、快速排序
     选择类：简单选择排序、堆排序
     归并类：二路归并排序
     基数类：多关键字排序
     九种算法的时间复杂度、空间复杂度和稳定性小结如下：
     在这里插入图片描述
     本文放出插入算法的三种排序算法代码。
     八种常用的排序算法代码可以到这里下载。
     

    直接插入排序
     

    void InsertSort(int R[], int n) {
	if (R == NULL || n <= 0)
		return;
	int i, j, temp;
	cout<<"直接插入排序："<<endl;
	for (i = 1; i < n; ++i) {
		temp = R[i];
		j = i - 1;
		while (j >= 0 && temp < R[j]) {
			R[j + 1] = R[j];
			--j;
		}
		R[j + 1] = temp;
		for (int k = 0; k < n; k++)
			cout << R[k] << " ";
		cout << endl;
	}
	cout << endl;
}

     

    折半插入排序
     

    void binaryInsertSort(int R[], int n) {
	if (R == NULL || n <= 0)
		return;
	int i, j, mid, low, high, temp;
	cout <<endl<< "折半插入排序：" << endl;
	for (i = 1; i < n; i++) {
		low = 0;
		high = i - 1;
		temp = R[i];
		while (low <= high) {
			mid = (low + high) / 2;
			if (R[mid] > temp) {
				high = mid - 1;
			}
			else {
				low = mid + 1;
			}
		}
		for (j = i - 1; j >= high + 1; j--) 
			R[j + 1] = R[j];
		R[high+1] = temp;
		for (int k = 0; k < n; k++)
			cout << R[k] << " ";
		cout << endl;
	}
	cout << endl;
}

     

    希尔排序
     

    void shellSort(int R[], int n){
	if (R == NULL || n <= 0)
		return;
	cout << endl << "希尔排序：" << endl;
	int len = n;
	while (len > 1)
	{
		len = len / 3 + 1;
		for (int i = len; i < n; i++)
		{
			int temp = R[i];
			if (R[i] < R[i - len])
			{
				int j;
				for (j = i - len; j >= 0 && R[j] > temp; j = j - len)
					R[j + len] = R[j];
				R[j +len] = temp;
			}
		}
		for (int k = 0; k < n; k++)
			cout << R[k] << " ";
		cout << endl;
	}
	cout << endl;
}

     

    总体
     

    #include <iostream>
using namespace std;
void InsertSort(int R[], int n) {
	if (R == NULL || n <= 0)
		return;
	int i, j, temp;
	cout<<"直接插入排序："<<endl;
	for (i = 1; i < n; ++i) {
		temp = R[i];
		j = i - 1;
		while (j >= 0 && temp < R[j]) {
			R[j + 1] = R[j];
			--j;
		}
		R[j + 1] = temp;
		for (int k = 0; k < n; k++)
			cout << R[k] << " ";
		cout << endl;
	}
	cout << endl;
}
void binaryInsertSort(int R[], int n) {
	if (R == NULL || n <= 0)
		return;
	int i, j, mid, low, high, temp;
	cout <<endl<< "折半插入排序：" << endl;
	for (i = 1; i < n; i++) {
		low = 0;
		high = i - 1;
		temp = R[i];
		while (low <= high) {
			mid = (low + high) / 2;
			if (R[mid] > temp) {
				high = mid - 1;
			}
			else {
				low = mid + 1;
			}
		}
		for (j = i - 1; j >= high + 1; j--) 
			R[j + 1] = R[j];
		R[high+1] = temp;
		for (int k = 0; k < n; k++)
			cout << R[k] << " ";
		cout << endl;
	}
	cout << endl;
}
void shellSort(int R[], int n){
	if (R == NULL || n <= 0)
		return;
	cout << endl << "希尔排序：" << endl;
	int len = n;
	while (len > 1)
	{
		len = len / 3 + 1;
		for (int i = len; i < n; i++)
		{
			int temp = R[i];
			if (R[i] < R[i - len])
			{
				int j;
				for (j = i - len; j >= 0 && R[j] > temp; j = j - len)
					R[j + len] = R[j];
				R[j +len] = temp;
			}
		}
		for (int k = 0; k < n; k++)
			cout << R[k] << " ";
		cout << endl;
	}
	cout << endl;
}
int main()
{
	int A[8] = { 49,38,65,97,76,13,27,49 };
	int n = 8;
	int R[8];
	cout << "原始数组：" << endl;
	for (int k = 0; k < n; k++) {
		R[k] = A[k];
		cout << R[k] << " ";
	}
	cout<< endl << endl;
	InsertSort(R, n); //直接插入排序
	for (int k = 0; k < n; k++) {
		R[k] = A[k];
		cout << R[k] << " ";
	}
	cout << endl;
	binaryInsertSort(R, n);  //折半插入排序
	for (int k = 0; k < n; k++) {
		R[k] = A[k];
		cout << R[k] << " ";
	}
	cout << endl;
	shellSort(R, n); //希尔排序

	return 0;
}

     

    主要参考的书籍是《数据结构高分笔记》2021版
    
                                    
    
                                    
    收起 
    
                                
    
                                        
                                            展开全文
                                            
                                        
                            
    
                                
    
                                    
                                        数据结构   
                                        排序算法   
                                
    

                        
    • 
                        
  • 
                            
    
                                
                                    
    排序3：插入排序(普通插入排序 + 折半插入排序 + 链表插入排序 + 希尔排序)
    
                                    
                                    
                                            千次阅读
                                    
                                2017-02-10 21:21:44
                            
    
                            
    
                                
    
                                    插入排序，包括普通插入排序、折半插入排序、链表插入排序、希尔排序的描述
                                
    
                                
    
                                    
    
                                        
    
                                    
    
                                    
    收起 
    
                                
    
                            
    
                                
    
                                    
                                        希尔排序   
                                
    

                        
    • 
                

            


            

                

                

                    
                    
空空如也

                

            


            

                

                

                    
                    
空空如也

                

            


            

                


 

 
 
         

            
                     


                    
                        1 
                    
                    
                        2 
                    
                    
                        3 
                    
                    
                        4 
                    
                    
                        5 
                    
                        ... 
                    
                        20 
                    

                    
            
        

   

                

                

            


        

    

    

        

            

                收藏数
                    680,097
            

            

                精华内容
                    272,038
            

        

        

            
热门标签

            
        


        


        

            关键字：
插入排序