保定中小企业网站制作,wordpress进入文字版,十大不收费的网站,邯郸做网站的地方C自学精简教程 目录(必读)
插入排序
每次选择未排序子数组中的第一个元素#xff0c;从后往前#xff0c;插入放到已排序子数组中#xff0c;保持子数组有序。
打扑克牌#xff0c;起牌。 输入数据
42 20 17 13 28 14 23 15
执行过程 完整代码
#include iostream…C自学精简教程 目录(必读)
插入排序
每次选择未排序子数组中的第一个元素从后往前插入放到已排序子数组中保持子数组有序。
打扑克牌起牌。 输入数据
42 20 17 13 28 14 23 15
执行过程 完整代码
#include iostream
#include cassert
#include vector
using namespace std;void print_array(const char* msg, int* arr, int n)
{cout msg ;for (int i 0; i n; i){cout arr[i] ;}cout endl;
}
//swap two number
void Swap(int a, int b)
{int tmp a; a b; b tmp;
}//将newValue插入到子数组arr中arr的长度为length
void Insert(int* arr, int newValueindex, int newValue)
{// newValueindex1 {arr[0]} arr[1] // newValueindex2 {arr[0], arr[1]} arr[2]// ......// newValueindexn-1 {arr[0], arr[1],... arr[n-2]} arr[n-1]// [a, b, c, d] e// 0 j length int j newValueindex - 1;for (; j 0; j--){if (arr[j] newValue){//move arr[j] to the next position,for newVaulearr[j 1] arr[j];}else{break;//break 发生时 j 的值可能是 0}}//发生了移动j会停止在最后一个需要被移动的位置的前面一个位置if (j ! newValueindex - 1){arr[j1] newValue;}
}void InsertSort(int* arr, int n)
{if (n 1){return;}//将下标为1的元素插入到{arr[0]}中//将下标为2的元素插入到{arr[0], arr[1]}中//......//将下标为n-1的元素插入到{arr[0], arr[1], arr[n-2]}中for (int i 1; i n; i) {//将未排序序列中的第一个元素插入到已排序的序列中Insert(arr, i, arr[i]);//insert first element in unsorted list to the sorted listprint_array(one trip, arr, n);}
}void test(vectorint arr)
{//输出原始序列print_array(original array:, arr.data(), arr.size());//执行排序,并输出排序过程InsertSort(arr.data(), arr.size());//输出排序后的列表print_array(after sorted:,arr.data(), arr.size());cout endl;
}int main()
{test({ 1 });test({ 1 , 2 });test({ 2 , 1 });test( { 2 , 2 });test({ 42, 20, 17, 13, 28, 14, 23, 15 });test({ 1, 8, 3, 6, 5, 4, 7, 2 , 9 });test( { 8, 8, 6, 6, 7, 5, 5, 7, 9 , 9});return 0;
}执行结果
original array: 1
after sorted: 1original array: 1 2
one trip 1 2
after sorted: 1 2original array: 2 1
one trip 1 2
after sorted: 1 2original array: 2 2
one trip 2 2
after sorted: 2 2original array: 42 20 17 13 28 14 23 15
one trip 20 42 17 13 28 14 23 15
one trip 17 20 42 13 28 14 23 15
one trip 13 17 20 42 28 14 23 15
one trip 13 17 20 28 42 14 23 15
one trip 13 14 17 20 28 42 23 15
one trip 13 14 17 20 23 28 42 15
one trip 13 14 15 17 20 23 28 42
after sorted: 13 14 15 17 20 23 28 42original array: 1 8 3 6 5 4 7 2 9
one trip 1 8 3 6 5 4 7 2 9
one trip 1 3 8 6 5 4 7 2 9
one trip 1 3 6 8 5 4 7 2 9
one trip 1 3 5 6 8 4 7 2 9
one trip 1 3 4 5 6 8 7 2 9
one trip 1 3 4 5 6 7 8 2 9
one trip 1 2 3 4 5 6 7 8 9
one trip 1 2 3 4 5 6 7 8 9
after sorted: 1 2 3 4 5 6 7 8 9original array: 8 8 6 6 7 5 5 7 9 9
one trip 8 8 6 6 7 5 5 7 9 9
one trip 6 8 8 6 7 5 5 7 9 9
one trip 6 6 8 8 7 5 5 7 9 9
one trip 6 6 7 8 8 5 5 7 9 9
one trip 5 6 6 7 8 8 5 7 9 9
one trip 5 5 6 6 7 8 8 7 9 9
one trip 5 5 6 6 7 7 8 8 9 9
one trip 5 5 6 6 7 7 8 8 9 9
one trip 5 5 6 6 7 7 8 8 9 9
after sorted: 5 5 6 6 7 7 8 8 9 9
