插入排序

标签：cout   参考   排序   部分   默认   取数   while   现在   长度   

直接插入排序

将待排序列分为已排序序列和未排序序列，不断取出未排序序列中的元素放入已排序序列中合适的位置（指放之后已排序序列仍然有序）。下面的例子中，是一个待排的数组arr，先将0位置的元素认为是一个有序序列，1~len(arr)-1为无序，慢慢从1开始取元素加入有序部分，直到所有数组元素有序。

#include 

using namespace std;

void insert_sort(int arr[], int len)
{
    int temp, i, j;
    for(i = 1; i =0 && arr[j]>k)       //在已排序序列内，查找k的大小位置
        {
            arr[j+1] = arr[j];       //将元素后移，为k腾出空位
            j--;                     //在已排序序列内，由后向前循环
        }
        arr[j+1] = temp;                //将需要排序的元素放到腾出的空位上
    }
}

int main()
{
    int arr[] = {7, 1, 4, 8, 3, 2};
    int len = sizeof(arr)/sizeof(int);
    for(int i = 0; i 

折半插入排序

在将一个新元素插入已排好序的数组的过程中，寻找插入点时，待插序列的首元素为arr[low]，末元素为arr[high]，比较时将待插入元素与arr[mid]（mid=(low+high)/2）相比较,如果比参考元素大，则选择arr[low]到arr[m-1]为新的插入区域(即high=mid-1)，否则选择arr[mid+1]到arr[high]为新的插入区域（即low=mid+1），如此直至low

#include 

using namespace std;

void binary_insert_sort(int arr[], int len)
{
    int k, i, j;
    int low, high, mid;
    for(i = 1; i = high+1 ; j--)       //元素会插在arr[high+1]这个位置，而从high到i-1的元素会后移
        {
            arr[j+1] = arr[j];
        }
        arr[j+1] = k;
    }

}

int main()
{
    int arr[] = {7, 1, 4, 8, 3, 2};
    int len = sizeof(arr)/sizeof(int);
    for(int i = 0; i 

希尔排序

又称为缩小增量排序。基本思路是将待排序列分割成若干个子序列，对每个子序列进行排序，然后缩小分割量（比如原本每隔4个元素为一组，现在变为2个），继续对缩小后的子序列排序，直到最后分割量为1。

#include 

using namespace std;

void shell_sort(int arr[], int len)
{
    int gap;          //步长
    int i, j;
    for(gap = len / 2; gap > 0; gap = gap / 2)        //先取数组arr长度的一半，然后每次变为上次的1/2。
    {
        for(i = gap; i = 0 && arr[j] > temp)
                {
                    arr[j+gap] = arr[j];
                    j = j - gap;
                }
                arr[j+gap] = temp;
            }
        }
    }
}

int main()
{
    int arr[] = {7, 1, 4, 8, 3, 2};
    int len = sizeof(arr)/sizeof(int);
    for(int i = 0; i 

注意点：从上面shell_insert()函数中截取一段（也是注释里需要注意那块），如下。

for(i = gap; i 

排序并不是将某个子序列完全排完，再下一个子序列。而是所有子序列轮着来orz

插入排序

标签：cout   参考   排序   部分   默认   取数   while   现在   长度   

原文地址：https://www.cnblogs.com/echobiscuit/p/12968900.html