asp.net中C++插入排序折半插入排序法例子

作者：袖梨 2022-06-25

C++插入排序包括折半插入排序法代码，在直接插入排序,数组data用于存放待排序元素，n为待排序元素个数，同时还包括了对data数组中的元素进行希尔排序，n为该数组大小等：

代码如下

复制代码

#include
using namespace std;
#include "sort.h"
// 直接插入排序,数组data用于存放待排序元素，n为待排序元素个数
template
void InsertSort(ElemType data[], int n)
{
    ElemType tmp;
int i, j;
    for (i = 1; i < n; i++){
        if ( data[i] > data[i - 1])
            continue;
        tmp = data[i];                                // 保存待插入的元素
  data[i] = data[i - 1];
        for ( j = i - 1; j > 0 && data[j - 1] > tmp;j--)
            data[j] = data[j - 1];                    // 元素后移
        data[j] = tmp;                                // 插入到正确位置
    }
}
// 折半插入排序
template
void BInsertSort(ElemType data[], int n)
{
    ElemType tmp;
int i, j, mid, low, high;
    for (i = 1; i < n; i++){
        tmp = data[i]; // 保存待插入的元素
        low = 0;
        high = i-1;
        while (low <= high){ // 在data[low..high]中折半查找有序插入的位置
            mid = (low + high) / 2; // 折半
            if( tmp < data[mid])
                high = --mid; // 插入点在低半区
            else
                low = ++mid; // 插入点在高半区
        }
        for(j = i - 1; j >= low; j--)
            data[j + 1] = data[j]; // 元素后移
        data[low] = tmp; // 插入到正确位置
    }
}
// 对data数组中的元素进行希尔排序，n为该数组大小
// increments为增量序列，incrementsLength为增量序列的大小
template
void ShellSort(ElemType data[], int increments[], int n, int incrementsLength)
{
    int i, j, k;
    ElemType tmp;
for ( k = 0; k < incrementsLength; k++){ // 进行以increments[k]为增量的排序
        for ( i = increments[k]; i < n; i++){
            tmp = data[i];
            for ( j = i; j >= increments[k]; j -= increments[k]){
                if ( tmp >= data[j - increments[k]])
                    break;
                data[j] = data[j - increments[k]];
            }
            data[j] = tmp;
        }
    }
}

补充一个

1.直接插入排序；2.折半插入排序；3.Shell排序；4.冒泡排序；5.快速排序；6.简单选择排序；7.堆排序；8.2-路归并排序；9.2-路归并排序（非递归）；10.基数排序等，程序代码如下：

代码如下

复制代码

#include "sort.h"
int main()
{
    cout << "---此程序实现排序---" << endl << endl;
    cout << "1.直接插入排序；2.折半插入排序；3.Shell排序；" << endl;
    cout << "4.冒泡排序；5.快速排序；" << endl;
    cout << "6.简单选择排序；7.堆排序；" << endl;
cout << "8.2-路归并排序；9.2-路归并排序（非递归）；10.基数排序；" << endl;
cout << "0.退出" << endl << endl;

    int n,select,*pData = NULL;
SLList list;
int* increments;

while (true){
  cout << "请选择排序算法：" << endl;
  cin >> select;
  switch ( select){
  case 1:
   n = init(&pData);
   InsertSort(pData,n);
   break;
  case 2:
   n = init(&pData);
   BInsertSort(pData,n);
   break;
  case 3:
   int incrementsLenth,i;
   cout << "请输入增量序列长度：" << endl;
   cin >> incrementsLenth;
   increments = new int[incrementsLenth];
   cout << "请输入增量序列：" << endl;
   for (i = 0; i < incrementsLenth; i++)
    cin >> increments[i];
   n = init(&pData);
   ShellSort( pData,increments,n,incrementsLenth);
   delete[] increments;
   break;
  case 4:
   n = init(&pData);
   BubbleSort(pData,n);
   break;
  case 5:
   n = init(&pData);
   QuickSort(pData,n);
   break;
  case 6:
   n = init(&pData);
   SelectionSort(pData,n);
   break;
  case 7:
   n = init(&pData);
   HeapSort(pData,n);
   break;
  case 8:
   n = init(&pData);
   MergeSort(pData,n);
   break;
  case 9:
   n = init(&pData);
   MergeSortNonRecursion(pData, n);
   break;
  case 10:
   n = init(&pData);
   list.Init(pData,n);
   list.RadixSort();
   list.Arrange();
   break;
   // RadixSort(pData,n);
   // break;
  case 0:
   system("pause");
   return 0;
  default:
   cout << "Input Error！"<< endl << endl;
   continue;
  }
  cout << "排序结果为：" << endl;
  if(select == 10)
   cout << list;
  else
   print( pData,0,n - 1);
  cout << endl;

  delete[] pData;
}
    system("pause");
    return 0;
}
int init(int** pData)
{
    int size,i;
    cout << "输入待排序元素个数" << endl;
    cin >> size;

    *pData = new int[size];

    cout << "输入待排序元素"<< endl;
    for(i = 0 ; i < size; i++)
        cin >> (*pData)[i];
    return size;
}
template
void print(ElemType data[],int begin,int end)
{
    for (int i = begin; i <= end; i++){
        cout << data[i] << " ";
    }
    cout << endl;
}