|
排序的方法有很多中，其中就包括一个比较重要的插入排序，他的思路就是像摸扑克牌一样，每次新的数据插入到相对应的位置之后，在整体把数据向后移，插入数据。自己总结和测试的代码如下：欢迎来指正
#include<iostream>
using namespace std;
#include<string>
//总结排序算法
//展示整体的数据
void ShowArray(int* a, int n)
{
?? ?cout << "数据为:" << endl;
?? ?for (int i = 0; i < n; i++)
?? ?{
?? ??? ?cout << a[i] << " ";
?? ?}
?? ?cout << endl;
}
//直接插入排序从小到大 ?
void InsertSort(int* a, int n)
{
?? ?int i = 1;
?? ?for (i = 1; i < n; i++)
?? ?{
?? ??? ?int temp = a[i];//记录要插入的数据
?? ??? ?int j = i - 1;//j最开始指向前一个数据
?? ??? ?while (temp < a[j])//控制条件把数据整体往后移动
?? ??? ?{
?? ??? ??? ?a[j + 1] = a[j];
?? ??? ??? ?j--;
?? ??? ?}
?? ??? ?a[j + 1] = temp;//插入到特定位置
?? ?}
?? ?cout << "1直接插入排序好的";
?? ?ShowArray(a, n);
}
//2折半插入排序算法
void BinsertSort(int* a, int n)
{
?? ?int i = 1;
?? ?for (i = 1; i < n; i++)
?? ?{
?? ??? ?int temp = a[i];
?? ??? ?int low = 0, high = i-1;//定义下标最左和最右
?? ??? ?while (low <= high)
?? ??? ?{
?? ??? ??? ?int mid = (low + high)/2;//中间下标
?? ??? ??? ?if (a[mid] <= temp)
?? ??? ??? ?{
?? ??? ??? ??? ?low = mid + 1;
?? ??? ??? ?}
?? ??? ??? ?else
?? ??? ??? ?{
?? ??? ??? ??? ?high = mid - 1;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?for (int j = i; j>low; j--)//在每一次找到插入位置后进行数据整体后移动，然后插入
?? ??? ?{
?? ??? ??? ?a[j] = a[j-1];
?? ??? ?}
?? ??? ?a[low] = temp;
?? ?}
?? ?cout << "2折半插入排序好的";
?? ?ShowArray(a, n);
}
//3二路插入排序算法
void Path2InsertSort(int* a, int n)
{
?? ?int* newarray = new int[n];//创建新数组指针
?? ?newarray[0] = a[0];//直接赋值第一个
?? ?int first = 0,last = 0;
?? ?for (int i = 1; i < n; i++)//对原本数组进行一个个插入
?? ?{
?? ??? ?if (a[i]>=newarray[last])//大于等于数据直接加入
?? ??? ?{
?? ??? ??? ?last++;//因为last可以直接往后加，不会超出
?? ??? ??? ?newarray[last] = a[i];
?? ??? ?}
?? ??? ?else if (a[i] < newarray[first])//小数据在后面，更小的话直接插入
?? ??? ?{
?? ??? ??? ?first = (first - 1 + n) % n;
?? ??? ??? ?newarray[first] = a[i];?? ?
?? ??? ?}
?? ??? ?else//插入的数据在l和f之间，则要移动然后插入
?? ??? ?{
?? ??? ??? ?int j = last;//定位最大的数的下标
?? ??? ??? ?while (a[i] < newarray[j])
?? ??? ??? ?{ ??
?? ??? ??? ??? ?//小的情况，则整体移动
?? ??? ??? ??? ?newarray[(j + 1)% n] = newarray[j];//用循环队列解决冲突，取余找出下标
?? ??? ??? ??? ?j = (j - 1 + n) % n;
?? ??? ??? ?}
?? ??? ??? ?newarray[(j + 1)%n] = a[i];//插入到此时需要插入的位置
?? ??? ??? ?last++;
?? ??? ?}
?? ?}
?? ?for (int i = 0; i < n; i++)
?? ?{
?? ??? ?a[i] = newarray[(first+i)% n];
?? ?}
?? ?delete []newarray;
?? ?cout << "3二路插入排序好的";
?? ?ShowArray(a, n);
}
int main()
{
?? ?int arr[10] = { 5,7,9,1,2,8,0,4,7,6 };
?? ?ShowArray(arr, 10);
?? ?//InsertSort(arr, 10);//插入排序
?? ?//BinsertSort(arr, 10);//折半插入排序
?? ?Path2InsertSort(arr, 10);//二路插入排序
?? ?return 0;
}
|