一聚教程网:一个值得你收藏的教程网站

热门教程

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

时间:2022-06-25 08:12:37 编辑:袖梨 来源:一聚教程网

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;
}

热门栏目