精华内容
下载资源
问答
  • 插入排序 C++

    2020-03-25 11:13:21
    目录插入排序的思路插入排序C++实现插入排序优化思路 插入排序的思路 对 A[0…n-1] 排序,只需要将 A[0…n-2] 排好序,然后把 A[n-1] 插入到已排序数组的合适位置即可 本质是基于Divid and Conquer 思路 Divid ...

    插入排序的思路

    • 对 A[0…n-1] 排序,只需要将 A[0…n-2] 排好序,然后把 A[n-1] 插入到已排序数组的合适位置即可
    • 本质是基于Divid and Conquer 思路
      • Divid 策略:基于元素下标
        • A[0…n-1] = A[0…n-2] + 一个单独的元素
        • A[0…n-2] 与 A[0…n–1] 有相同的结构,但是规模更小
        • 对 A[0…n-2] 排序构成原问题的 sub-problem
    • 时间复杂度
      • 最坏:所有元素都逆序排列,O(n) = O(n^2)
      • 最好:所有元素都顺序排列:O(n) = n
      • 平均:O(n^2)

    插入排序的C++实现

    #include<iostream>
    #include<vector>
    
    using namespace std;
    void InsertSort(vector<int>& v){
        if(v.empty())
            return;
        int v_len = v.size();
        // default:v[0] is sorted
        for(int i = 1; i < v_len; i++){
            int insert_key = v[i];
            int j = i-1;
            while(j >= 0 && insert_key < v[j]){
                v[j+1] = v[j];
                j--;
            }
            v[j+1] = insert_key;
        }
    }
    int main(){
        vector<int> v{1,3,8,5,7,4};
        InsertSort(v);
        for(int val:v)
            cout<<val<<" ";
        return 0;
    }
    
    

    插入排序优化思路

    • 子问题数量上减小得太慢,每次只减一个元素,因此需要依次减少 n 次,每次又要比较最多 n 个元素,造成 O(n^2) 的时间复杂度
    • Divid 策略 2:基于元素的下标
      • A[0…n-1] = A[0…n/2 -1] + A[n/2…n-1]
      • 子问题每次变为原问题的一半,即 归并排序 的思想

    此篇文章为卜东波老师的算法课总结。

    展开全文
  • 插入排序C++

    2019-03-03 09:39:13
    代表待插入数字的下标; preIndex.........代表前一个元素的下标; length...........代表数组的长度 排序过程: arr[0]跳过,从arr[1]开始,每一个数都和它前面的数字比较。 while(i&amp;amp;lt;length){//...

    1、算法描述

    /*
    变量:
    i=1..............代表待插入数字的下标;
    preIndex.........代表前一个元素的下标;
    length...........代表数组的长度
    排序过程:
    arr[0]跳过,从arr[1]开始,每一个数都和它前面的数字比较。
    while(i<length){//遍历数组arr[1]...arr[length-1]
    	preIndex=i-1
    	若arr[preIndex]<=arr[i],那么前小后大,有序,i++
    	若arr[preIndex]>arr[i],那么前大后小,乱序
    	{
    		current=arr[i]//记录下待插入的数值
    		arr[i]=arr[preIndex]
    		preIndex--;
    	while(preIndex>=0&&arr[preIndex]>tem)//preIndex不小于0且arr[preIndex]>tem
    	{
    		arr[preIndex+1]=arr[preIndex]
    		preIndex--
    	}
    	arr[preIndex+1]=current;
    	i++;
    
    }
    }
    */
    

    2、C++实现

    #include<iostream>
    using namespace std;
    void insertsort(int arr[],int length) {
    	int i = 1;
    	while (i<length)
    	{
    		int preIndex = i - 1;
    		if (arr[preIndex] > arr[i])//前大后小
    		{
    			int current = arr[i];//记录待插入的数值
    			while (preIndex >= 0 && arr[preIndex] > current)
    			{
    				arr[preIndex + 1] = arr[preIndex];//将arr[preIndex]后移一位
    				preIndex = preIndex - 1;
    			}
    			arr[preIndex + 1] = current;
    		}
    		i += 1;
    		
    	}
    }
    int main() {
    	int arr[] = { 9,3,1,18,3,2,1,0,13,18,100 };
    	int length = sizeof(arr) / sizeof(arr[0]);
    	cout << "排序前数组为:" << endl;
    	for (int i = 0; i < length; i ++) {
    		cout << arr[i];
    		cout << "\t";
    	}
    	cout << endl;
    	insertsort(arr, length);
    	cout << "排序后数组为:" << endl;
    	for (int i = 0; i < length; i++) {
    		cout << arr[i];
    		cout << "\t";
    	}
    	system("PAUSE");
    
    }
    
    展开全文
  • 插入排序 c++

    2011-02-25 17:19:00
    /*插入排序*/#include#include#include#include#define MAXI 10typedef int KeyType;typedef int ElemType;struct rec{ KeyType key; ElemType data;};typedef rec sqlist[MAXI];class c

     /*

    插入排序
    */
    #include<iostream.h>
    #include<iomanip.h>
    #include<time.h>
    #include<stdlib.h>
    #define MAXI 10
    typedef int KeyType;
    typedef int ElemType;
    struct rec{
    KeyType key;
    ElemType data;
    };
    typedef rec sqlist[MAXI];
    class charu
    {//类定义
    public:
    charu(sqlist a, int m):n(m)
    {
    for(int i=0; i<n; i++)
    b[i]=a[i];
    }
    void insertsort()
    {
    int i,j,k;
    for(i=1;i<n;i++)
    {
    rec d=b[i];
    for(j=i;j>0 && b[j-1].key>d.key;j--)
    b[j]=b[j-1];
    b[j]=d;
    for(k=0;k<n;k++)
    cout<<setw(4)<<b[k].key;
    cout<<endl;
    }
    }
    void output()
    {
    for(int i=0;i<n;i++)
    cout<<setw(4)<<b[i].key;
    cout<<endl;
    }
    private:
    sqlist b;
    int n;
     
    };
     
    void main()
    {
    cout<<"运行结果:/n";
    sqlist a1;
    int i;
    srand(time(0));
    for(i=0;i<10;i++)
    {
    a1[i].key=rand()%100;
    a1[i].data=rand()%80;
    }
    charu px(a1,10);
    cout<<"排序前数组/n";
    px.output();
    cout<<"排序过程演示:/n";
    px.insertsort();
    cout<<"排序后数组/n";
    px.output();
    cin.get();
    }
    展开全文
  • 插入排序 C++实现

    2020-02-18 01:43:36
    插入排序 C++实现 1、算法思路:以我们日常打扑克牌为例,如果我们要将手中没有排序的扑克牌从小到大排序,通常的做法就是我们首先拿第二张牌与第一张牌作比较,如果第二张牌比第一张小,那就把第二张放到第一张的...

    插入排序 C++实现

    1、算法思路:以我们日常打扑克牌为例,如果我们要将手中没有排序的扑克牌从小到大排序,通常的做法就是我们首先拿第二张牌与第一张牌作比较,如果第二张牌比第一张小,那就把第二张放到第一张的前面,如果第二张比第一张大,那就不用换位置;第一、二张排好以后,拿起第三张,先与第二张作比较,再与第一张作比较,依次类推;
    2、难点:控制要比较的牌与前面每一张牌都要比较,其实也很简单,要是数组的话,加个下标计数器依次递减即可。
    3、代码实现:
    #include
    using namespace std;
    int main(){
    int a[6] = { 5, 2, 4, 6, 1, 3 };
    for (int j = 1; j<6; j++){
    int key = a[j];
    int i = j - 1;
    while (i >= 0 && a[i]>key){
    a[i + 1] = a[i];
    i = i - 1;
    a[i + 1] = key;
    }
    }
    for (int i = 0; i <= 5; i++){
    cout << a[i] << " ";
    }
    return 0;
    }

    展开全文
  • 归并排序,插入排序,以及两种排序算法的结合C++实现
  • 插入排序C++实现

    2015-04-12 17:11:55
    网上有很多讲插入排序的算法,但大多数都没有提供完整的程序,于是我在业余时间参考网上资料写了一个插入排序的完整C++实现,在VC6.0++编译通过,大家打开压缩文件点击sort.dsw文件打开即可编译运行,代码也有详解的...
  • 插入排序 c++ insertsort

    2011-07-15 17:19:22
    插入排序 插入排序 插入排序 插入排序 插入排序 dfdsfdsffdsf fdsfdsf dfsdfdsf
  • 插入排序 C++源码

    2011-09-30 23:01:57
    插入排序c++实现,有注释,输入未排序double数组,输出排序好的double数组,由小到大排序
  • 直接插入排序通过键盘输入建立数组,再经过直接插入排序算法进行排序。在VS上X64编译通过。直接插入排序算法理论参考《算法导论》和张琨的《数据结构与算法分析(C++语言版)》
  • 数据结构排序算法中的插入排序,是比较简单比较基础的一个排序算法
  • 插入排序 C++

    2018-11-03 17:52:38
    一、说明:插入排序的原理在注释中,插入排序中使用了模板来传入数据,详细情况看下面的测试代码。 #include &amp;lt;iostream&amp;gt; #include &amp;lt;vector&amp;gt; using namespace std;...
  • 文章目录插入排序(Insertion Sort)1.直接插入排序(Straight Insertion Sort)1.1 算法描述1.2 复杂度1.3 代码实现2.折半插入排序(Binary Insertion Sort)3.希尔排序(Shell Sort)3.1 算法基本思想3.2 算法流程3.3 ...
  • LeetCode 147. Insertion Sort List 链表插入排序 C++/Java Sort a linked list using insertion sort. A graphical example of insertion sort. ...
  • 直接插入排序c++

    2017-08-29 14:02:57
    1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想:将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个...
  • 插入排序算法也是一个复杂度为O(n^2)的排序算法,它的原理跟打扑克类似。在打扑克时,每摸到一张牌我们都会把它插入到手上扑克中的正确位置。那么在排序中就是进行两重循环,第一重循环遍历数组,第二重循环将当前...
  • 直接插入排序 C++实现

    2020-05-19 22:13:38
    插入排序的基本操作是“有序插入”,也就是将元素逐一插到有序序列中,保持序列有序,从而使有序序列的长度不断增加。 对数组a[n]排序时,起初a[0]被认为是长度为1的有序子序列。然后,按照有序插入法,i从1到n-1循环...
  • 插入排序 c++实现

    2017-12-20 08:56:02
    插入排序的重点在于从后往前面的有序列推进,需要注意到达终点时的处理与其他不同。 #include using namespace std; int arr[1001]; void insert_sort(int n){ int tmp; for(int i = 1; i ; i++){ tmp = ...
  • 直接插入排序C++实现

    2020-02-22 15:59:43
    直接插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。 设数组为a[0…n-1]。 1.初始时,a[0]自成1个有序区...
  • 插入排序 自己写着玩 防止忘记 传网上吧 可以直接用 不用四处找了
  • 直接插入排序 C++

    2017-06-28 18:24:49
    //直接插入排序 #include using namespace std;void insertSort(int arr[], int length) { int i,j,key; for(i=0;i;i++){ key = arr[i]; for(j=i-1;j>=0;j--){ if(ke
  • 今天看书时写了一个插入排序的代码,拿出来晒晒,有什么不足的地方,还请各位高手指出。 1 #include<iostream> 2 using namespace std; 3 void main() 4 { 5 int CS[50]; int i=0,n; 6 while (cin>>...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,346
精华内容 2,138
关键字:

插入排序c++

c++ 订阅