数据结构 | 排序问题之插入排序

1. 直接插入排序:

每次从无序表中取出最后一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

1. 详解：

从数组的第二个元素开始,将数组中的每一个元素按照（升序或者降序）规则插入到已排好序的数组中以达到排序的目的.

一般情况下将数组的第一个元素作为起始元素,从第二个元素开始依次插入。

由于要插入到的数组是已经排好序的,所以只要从右向左（或者从后向前）找到排序插入点插入元素，以此类推，直到将最后一个数组元素插入到数组中,整个排序过程完成。

2. 原理过程图（升序排列为例）

每次将数组最后一个元素作为插入元素，与它前面有序（已排好序）的数组元素进行比较后，插入正确的位置，排序完成。（如下图）

void lnsertSort(SeqList R)  
 { //对顺序表R中的记录R[1..n]按递增序进行插入排序  
  int i，j；  
  for(i=2;i<=n；i++) //依次插入R[2]，…，R[n]  
    if(R[i].key<R[i-1].key){//若R[i].key大于等于有序区中所有的keys，则R[i]  
                            //应在原有位置上  
      R[0]=R[i];j=i-1; //R[0]是哨兵，且是R[i]的副本  
      do{ //从右向左在有序区R[1．．i-1]中查找R[i]的插入位置  
       R[j+1]=R[j]； //将关键字大于R[i].key的记录后移  
       j-- ；  
       }while(R[0].key<R[j].key)； //当R[i].key≥R[j].key时终止  
      R[j+1]=R[0]； //R[i]插入到正确的位置上  
     }//endif  
 }//InsertSort  

哨兵的作用:

1. 进入查找(插入位置)循环之前，它保存了 R[i]的副本，使不致于因记录后移而丢失 R[i]的内容；
2. 在查找循环中”监视”下标变量j是否越界。一旦越界(即 j=0)，因为 R[0].key和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件”j>=1”)。

2. 希尔排序

希尔排序算法是按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布，是插入排序的一种更高效的改进版本。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步（增量较大）间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为 1 ，这样记录移动次数大大减少，提高了排序效率。希尔排序对增量序列的选择没有严格规定。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率
• 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位

实例分析:

假设有数组 array = [80, 93, 60, 12, 42, 30, 68, 85, 10]，首先取 d1 = 4，将数组分为 4 组，如下图中相同颜色代表一组：

然后分别对 4 个小组进行插入排序，排序后的结果为：

然后，取 d2 = 2，将原数组分为 2 小组，如下图：

然后分别对 2 个小组进行插入排序，排序后的结果为：

最后，取 d3 = 1，进行插入排序后得到最终结果：

#include <iostream>

using namespace std;

int a[] = {70,30,40,10,80,20,90,100,75,60,45};

void shell_sort(int a[],int n);
int main()
{
	cout<<"Before Sort: ";
    for(int i=0; i<11; i++)
		 cout<<a[i]<<" ";
	  cout<<endl;
	  shell_sort(a, 11);
   cout<<"After Sort: ";
	  for(int i=0; i<11; i++)
		  cout<<a[i]<<" ";
	  cout<<endl;
	 system("pause");
}

void shell_sort(int a[], int n)
{
	int gap;
	for(gap = 3; gap >0; gap--)
	{
		for(int i=0; i<gap; i++)
		{
			for(int j = i+gap; j<n; j=j+gap)
			{
				if(a[j]<a[j-gap])
				{
					int temp = a[j];
					int k = j-gap;
					while(k>=0&&a[k]>temp)
					{
						a[k+gap] = a[k];
						k = k-gap;
					}
					a[k+gap] = temp;
				}
			}
		}
	}
}