精华内容
下载资源
问答
  • 排序算法c++实现

    2020-04-13 22:53:00
    1.插入排序 //插入排序 #include<iostream> #include<vector> using namespace std; int main() { int n; vector<int> v; do { cin >> n; v.push_back(n); } while (getchar() != '\...

    1.插入排序

    //插入排序
    #include<iostream>
    #include<vector>
    using namespace std;
    int main()
    {
     int n;
     vector<int> v;
     do
     {
      cin >> n;
      v.push_back(n);
     } while (getchar() != '\n');//获取长度未知的输入数组
     //从第二个数开始将v[i]插入到前面已经排序好的i-1个数里
     for (int i = 1; i < v.size(); i++)
     {
      //将v[i]与v[i-1]依次比较小于就交换往前插,再与v[i-2]比较……最终插入到不大于v[i]的数的后面
      for (int j = i; j > 0; j--)
      {
       if (v[j] < v[j - 1])
       {
        int temp = v[j];
        v[j] = v[j - 1];
        v[j - 1] = temp;
       }
       else
        break;
      }
     }
     for (int i = 0; i < v.size(); i++)
      cout << v[i] << " ";
    }

    2.冒泡排序

    //冒泡排序
    #include<iostream>
    #include<vector>
    using namespace std;
    int main()
    {
     int n;
     vector<int> v;
     do
     {
      cin >> n;
      v.push_back(n);
     } while (getchar() != '\n');//获取长度未知的输入数组
     //每次将第i+1小的数往前,就像泡泡往上冒
     for (int i = 0; i < v.size()-1; i++)
     {
      //将剩下数中最小的往前排
      for (int j = v.size() - 1; j > i; j--)
      {
       if (v[j] < v[j - 1])
       {
        int temp = v[j];
        v[j] = v[j - 1];
        v[j - 1] = temp;
       }
       else
        break;
      }
     }
     for (int i = 0; i < v.size(); i++)
      cout << v[i] << " ";
    }

    3.选择排序

    //选择排序
    #include<iostream>
    #include<vector>
    using namespace std;
    int main()
    {
     int n;
     vector<int> v;
     do
     {
      cin >> n;
      v.push_back(n);
     } while (getchar() != '\n');//获取长度未知的输入数组
     //每次选择未排序序列中最大的数放在最后一位,l-1次后完成排序
     int l = v.size();
     for (int i = 1; i < l; i++)
     {
      //选择最大数放在最后
      for (int j = 0; j <= l-i; j++)
      {
       if (v[l-i] < v[j])
       {
        int temp = v[j];
        v[j] = v[l-i];
        v[l-i] = temp;
       }
      }
     }
     for (int i = 0; i < v.size(); i++)
      cout << v[i] << " ";
    }

    4.随机选择排序

    //随机快速排序
    #include<iostream>
    #include<vector>
    using namespace std;
    void quicksort(vector<int>& v, int left, int right)
    {
     if (left >= right) return;
     int ri = rand() % (right - left + 1) + left;//随机选取数组中数作为比较参考数/基准数/主元
     int temp = v[ri];
     v[ri] = v[left];
     v[left] = temp;
     int i = left, j = right;
     int base = v[left];
     while (i < j)
     {
      while (v[j] >= base && i<j) j--;//基准数在左,从右向左找小于参考数的数
      while (v[i] <= base && i<j) i++;//从左向右找大于参考数的数
      if (i < j)
      {
       temp = v[i];//交换使得参考数左边全是小于参考数的数,右边全是大于参考数的数
       v[i] = v[j];
       v[j] = temp;
      }
     }
     v[left] = v[i];
     v[i] = base;
     quicksort(v, left, i - 1);
     quicksort(v, i + 1, right);
    }
    int main()
    {
     int n;
     vector<int> v;
     do
     {
      cin >> n;
      v.push_back(n);
     } while (getchar() != '\n');//获取长度未知的输入数组
     quicksort(v, 0, v.size() - 1);
     for (int i = 0; i < v.size(); i++)
      cout << v[i] << " ";
    }
    展开全文
  • void SelectSort(int *num, int length) { for (int i= 0; i < length; i++) { int mindex = i; for (int j = i + 1; j < length; j++) { if (num[j] < num[mindex]) { ...}
  • 七大排序算法c++实现

    2018-10-03 23:40:39
    七大排序算法C++实现,包括冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序。代码随机生成数组来排序,MAX1定义了数组个数,用QueryPerformanceCounterday打印除了各算法用时。
  • sortaglorithm 数据结构中基本的排序算法c++实现
  • 前言 把排序算法忘光了,回顾《数据结构》严蔚敏版,并看了网上的几篇文章后,随再做一次总结。...排序算法C++实现 1.插入排序 1.1.直接插入排序 /* 直接插入排序 int ai[] 为需要排序的数组 sta...

    前言

    把排序算法忘光了,回顾《数据结构》严蔚敏版,并看了网上的几篇文章后,随再做一次总结。本文不会具体介绍每一个算法,我觉得要具体看,可以看《数据结构》这本书,写得很好,不懂的再百度补充知识,主要是每一种方式的实现展示出来。

     

    å¨è¿éæå¥å¾çæè¿°

    他们的性能比较:

    排序算法C++实现

    1.插入排序

    1.1.直接插入排序

    /*
    	直接插入排序
    	int ai[] 为需要排序的数组
    	start 为起始位置,要求 start>=1 ,因为 ai[0] 要作为“哨兵”使用。
    	end 为结束位置
    
    	代码思路:看后面的数字有没有比前面的大,比前面的大则需要插入交换,从后往前,依次比较,依次往后移一位,直到不满足
    
    */
    void InsertSort(int ai[] , int start , int end)
    {
    	int i , j ; 
    	for(i=start; i<=end; i++){
    		if(ai[i]<ai[i-1]){
    			ai[0] = ai[i] ; 
    			ai[i] = ai[i-1] ; 
    			for(j=i-2; ai[j]>ai[0]; j--){
    				ai[j+1] = ai[j] ; 
    			}
    			ai[j+1] = ai[0] ; 
    		}
    	}
    }
    

    1.2.希尔排序

    /**
     * 希尔排序
     * 分组插入排序、时间复杂度取决于所取“增量”序列函数、不稳定
     * 增量序列中的值没有除 1 之外的公因子,并且最后一个增量值必须等于 1 。
    */
    void ShellInsert(int ai[], int start, int end, int dt)
    {
    	int i, j ; 
    	for(i=start+dt; i<=end; i++){
    		if(ai[i] < ai[i-dt]){
    			ai[0] = ai[i];
    			for(j=i-dt; j>0 && ai[0]<ai[j]; j-=dt){
    				ai[j+dt] = ai[j] ; 
    			}
    			ai[j+dt] = ai[0] ; 
    		}
    	}
    }

    1.3折半插入排序

    
    /**
     * 折半插入排序
     * 不论初始序列情况如何,在插入第 i 个记录时,需要经过 log2i + 1 次比较
     * 折半插入排序仅减少了关键字间的比较次数,而记录的移动次数不变
     * 
    */
    void BInsertSort(int ai[] , int start , int end)
    {
    	int i,j ; 
    	for(i=start; i<=end; i++){
    		if(ai[i] < ai[i-1]){
    			ai[0] = ai[i] ; 
    			int low = 1, high = i-1  ;
    			while(low<=high){
    				int mild = (low + high)/2 ; 
    				if(ai[mild] > ai[0]){
    					high = mild - 1 ; 
    				}else {
    					low = mild + 1 ; 
    				}
    			}
    
    			for(j=i-1; j>=high+1; j--){
    				ai[j+1] = ai[j] ; 
    			}
    			ai[j+1] = ai[0];
    		}
    	}
    }
    

    2.交换排序

    2.1.冒泡排序

    
    /**
     * 冒泡排序
     * 两两比较相邻数的大小,逆序则交换,从而使最小的数如气泡一般逐渐上升,或者最大的数逐渐“坠落“
     * int a[]为需要排序的数组
     * start为起始位置,要求start>=1
     * end为结束位置
     */
    void BubbleSort(int ai[], int start, int end)
    {
    	bool flag = true ; 
    	for(int i=start; i<=end-1 && flag; i++)
    	{
    		flag = false ; 
    		for(int j=start; j<=end-i; j++){
    			if(ai[j] > ai[j+1]){
    				flag = true ;
    				int t = ai[j]; ai[j] = ai[j+1]; ai[j+1] = t;
    			}
    		}
    	}
    }
    

    2.2.快速排序

    
    /**
     * 快速排序
     * 一次排序消除多个逆序
     * 递归,分治法
     */
    int Partition(int ai[], int low, int high)
    {
    	int privotkey = ai[low];
    	while(low<high){
    		while(low<high && ai[high] >= privotkey) high--;
    		ai[low] = ai[high];
    		while(low<high && ai[low] <= privotkey) low++;
    		ai[high] = ai[low];
    	}
    	ai[low] = privotkey;
    	return low;
    }
    
    void Qsort(int ai[], int low, int high)
    {
    	if(low < high){
    		int pivotloc = Partition(ai,low,high); // 将 ai 一分为二,pivotloc 是枢轴位置
    		Qsort(ai, low, pivotloc-1); 
    		Qsort(ai, pivotloc+1, high);
    	}
    }
    

    3.选择排序

    3.1.简单选择排序

    
    /**
     * 简单选择排序
     * 找到最小的与相应第一个交换
     * 
     */
    void SelectSort(int ai[], int start, int end)
    {
    	for(int i=start; i<end; i++){// n-1 次比较
    		int k = i ; 
    		for(int j=i+1; j<=end; j++){
    			if(ai[j] < ai[k]) k = j ;
    		}
    		if(k != i){
    			int t = ai[i] ; ai[i] = ai[k] ; ai[k] = t ; 
    		}
    	}
    }

    3.1.堆排序

    
    /**
     * 堆排序,大根堆,升序,完全二叉树
     * 筛选法,初建堆从 n/2 开始从下往上,父节点大于子节点
     * 堆排序,调整堆,从 1 往下,交换了则需要继续往下递归,否则跳出。
     * 最坏O(nlog2n),而快排最坏O(n^2),当记录较多时较为高效
    */
    
    void HeapAdjust(int ai[],int start,int end)
    {
    	int rc = ai[start] ; 
    	for(int i=2*start; i<=end; i*=2){
    		if(i < end && ai[i] < ai[i+1]) i++;
    		if(rc > ai[i]) break ;
    		ai[start] = ai[i]; start = i; 
    	}
    	ai[start] = rc ;
    }
    
    void CreateHeap(int ai[],int end)
    {
    	for(int i=end/2; i>0; i--){
    		HeapAdjust(ai,i,end) ; 
    	}
    }
    
    void HeapSort(int ai[],int end)
    {
    	CreateHeap(ai,end);
    	for(int i=end; i>0; i--){
    		ai[0] = ai[1];
    		ai[1] = ai[i];
    		ai[i] = ai[0];
    		HeapAdjust(ai,1,i-1) ; 
    	} 
    }

    4.归并排序

    
    /**
     * 归并排序
     * int ai[]为需要排序的数组
     * cnt为求逆序对数目,是归并排序的拓展
    */
    int cnt = 0 ; 
    // 合并 ai 数组,排好序,临时存放在 temp 数组里,然后再拷贝到原来的数组 ai 
    void Merge(int ai[], int L, int mild, int R)
    {
    	int *temp = new int[R-L+1] ; 
    	int k = L, i = L, j = mild + 1 ; 
    	while(i<=mild && j <= R){
    		if(ai[i]<=ai[j]) temp[k++] = ai[i++];
    		else{
    			temp[k++] = ai[j++];
    			cnt += mild - i + 1 ;
    			/**
    			 * 举个例子: A=1,4,6,7,9 B=2,3,5,10,13,21.在Merge中发现当前i号元素4比2大,那么4的逆序数需要+1,又因6,7,9都排在4后面,那么6,7,9的逆序数也应该+1,
    			 * 所以总体的逆序数应该加上last-i+1.(如果i号元素比B[j]小(比如4比5小),无法确定逆序数的变化,不作任何修改).
    			*/
    		}
    	}
    	while(i<=mild) temp[k++] = ai[i++] ; 
    	while(j<=R) temp[k++] = ai[j++];
    	
    	for(int i=L;i<k;i++){
    		ai[i] = temp[i] ; 	
    	}
    }
    // 归并排序,将 ai 数组前半部分后半部分分成最小单元,然后在合并
    void MergeSort(int ai[], int L, int R)
    {
    	if(L==R){
    		return ;
    	} else {
    		int mild = (L + R) / 2 ; 
    		MergeSort(ai,L,mild); 
    		MergeSort(ai,mild + 1, R);
    		Merge(ai,L,mild,R);
    	}
    }
    

    5.基数排序

    
    /**
     * 基数排序
     * 分配 + 收集
     * 分配:我们将 ai[] 中的元素取出,首先确定其个位上的数字,根据该数字分配到与之序号相同的桶中 range 
     * 收集:当序列中所有的元素都分配到对应的桶中,再按照顺序依次将桶中的元素收集形成新的一个待排序列 ai[ ]
     * 需要知道各级关键字的主次关系和各级关键字的取值范围
    */
    void countSort(int ai[], int exp, int len)
    {
    	vector<int> range[10] ; 
    
    	for(int i=1; i<=len; i++){ // 分配
    		int t = (ai[i]/exp)%10 ; 
    		range[t].push_back(ai[i]);
    	}
    
    	int ant = 1 ;
    	for(int i=0; i<10; i++){ // 收集
    		for(int j=0;j<range[i].size();j++){
    			ai[ant++] = range[i][j] ;
    		}
    	}
    
    }
    
    void RadixSort(int ai[],int start, int end)
    {
    	
    	int maxn = -1 ; 
    	int len = end - start + 1 ; 
    	for(int i=start; i<end; i++){ // 提取出最大值
    		maxn = max(maxn,ai[i]) ; 
    	}
    
    	for(int exp=1; (maxn/exp)> 0; exp*=10){
    		countSort(ai,exp,len) ; 
    	}
    	
    }
    

    主函数

    
    int main()
    {
        int ai[] = {0,49,38,65,97,76,13,27,49};
    	/**
    	 * 插入排序
    	 * InsertSort(ai,2,8) ; // 直接插入排序
    	 * BInsertSort(ai,2,10) ; // 折半插入排序
    	 * ShellSort(ai,1,10); // 希尔排序
    	*/
    
    	/** 
    	 * 交换排序
    	 * BubbleSort(ai,1,10) ; // 冒泡排序 
    	 * Qsort(ai,1,10) ; // 快速排序
    	 */
    
    	/**
    	 * 选择排序
    	 * SelectSort(ai,1,10); // 简单选择排序
    	 * HeapSort(ai,8) ;  // 堆排序
    	*/
    
    	/**
    	 * MergeSort(ai,1,8) ; // 归并排序
    	 * RadixSort(ai,1,8) ; // 基数排序
    	*/
    	
    	
    	for(int i=1;i<=8;i++){
    		cout<<ai[i]<<" "; 
    	}
    	cout<<endl; 
    
    	return 0 ; 
    }

    参考

    《数据结构》严蔚敏版

    数据结构常见的八大排序算法(详细整理)

    展开全文
  • 经典排序算法C++实现

    2016-04-15 22:31:06
    经典排序算法C++实现用c++实现了经典的冒泡排序、插入排序、选择排序、堆排序、快速排序、希尔排序、归并排序。等空闲的时候再补充每个排序算法的思想以及易错点。常用的排序算法C++实现//冒泡排序 void bubble_sort...

    经典排序算法C++实现

    用c++实现了经典的冒泡排序、插入排序、选择排序、堆排序、快速排序、希尔排序、归并排序。等空闲的时候再补充每个排序算法的思想以及易错点。

    常用的排序算法C++实现

    //冒泡排序
    void bubble_sort(vector<int> arr, int N){
        vector<int> a(arr);
        int swaped = 0;
        //进行n-1次排序
        for(int i=0; i<N-1; i++){
            //处理未排序的部分
            for(int j=0; j<N-1-i; j++){
                if(a[j] > a[j+1])
                {
                    int temp = a[j+1];
                    a[j+1] = a[j];
                    a[j] = temp;
                    swaped = 1;
                }
            }
            if(swaped == 0)
                break;
            else
                swaped = 0;
        }
    }
    
    //插入排序
    //without sentinel
    void insert_sort(vector<int> arr, int N){
        vector<int> a(arr);
        int i,j;
        int temp;
        for(i=1; i<=N-1; i++){
            temp = a[i];
            for(j=i-1; j>=0 && a[j] > temp; j--){
                a[j+1] = a[j];
            }
            a[j+1] = temp;
        }
    }
    
    //with sentinel(有哨兵的插入排序)
    /*void insert_sort(vector<int> &a, int N){
        int i,j;
        //int temp;
        for(i=1; i<=N-1; i++){
            //temp = a[i];
            a[0] = a[i];
            for(j=i-1; a[j] > a[0]; j--){
                a[j+1] = a[j];
            }
            a[j+1] = a[0];
        }
    }*/
    
    //选择排序
    void selection_sort(vector<int> arr, int N){
        vector<int> a(arr);
        for(int i=0; i<N-1; i++){
            int min_pos = i;
            for(int j=i+1; j<N; j++){
                if(a[j] < a[min_pos]){
                    min_pos = j;
                }
            }
            if(min_pos != i){
                int temp = a[i];
                a[i] = a[min_pos];
                a[min_pos] = temp;
            }
        }
    }
    
    //快速排序
    void quick_sort(vector<int> &a, int left, int right)
    {
        //错误点2,没有对传入参数进行判断,导致left==right的时候,还会继续递归调用quick_sort()
        if(left >= right)
        {
            return;
        }
        int key = a[left];
        int low=left;
        int high=right;
        while(low < high)
        {
        //错误点1,外循环的low<high并不能保证内部循环的low<high
            while(low < high && a[high] >= key) high--;
            if(low < high)
                a[low++] = a[high];
            while(low < high && a[low] <= key) low++;
            if(low < high)
                a[high--] = a[low];
        }
        a[low] = key;
        quick_sort(a, left, low-1);
        quick_sort(a, low+1, right);
    }
    
    //归并排序
    void my_merge(vector<int> &a, int low, int high, int mid)
    {
        if(low >= high)
            return;
        int i=low;
        int j=mid+1;
        vector<int> vec;
        while(i<=mid && j<=high){
            if(a[i] <= a[j]){
                vec.push_back(a[i]);
                i++;
            }
            else{
                vec.push_back(a[j]);
                j++;
            }
        }
        while(i<=mid)   vec.push_back(a[i++]);
        while(j<=high) vec.push_back(a[j++]);
        //易错点,归并后的vec要复制到a对应的位置上去,不能简单直接赋值
        for(int k = 0; k<vec.size(); k++)
            a[k+low] = vec[k];
    }
    void merge_sort(vector<int> &a, int left, int right){
        if(left >= right)
            return;
        int mid = (left+right)/2;
        merge_sort(a, left, mid);
        merge_sort(a, mid+1, right);
        my_merge(a, left, right, mid);
    }
    
    //堆排序
    void max_heapify(vector<int> &arr, int i, int heap_size){
        int left=2*i+1;
        int right=left+1;
        int largest;
        if(left < heap_size && arr[left] > arr[i])
            largest = left;
        else
            largest = i;
        if(right < heap_size && arr[right] > arr[largest])
            largest = right;
        if(largest != i){
            swap(arr[largest], arr[i]);
            max_heapify(arr, largest, heap_size);
        }
    }
    void build_heap(vector<int> &arr){
        int heap_size = arr.size();
        for(int i=heap_size/2-1; i>=0; i--)
            max_heapify(arr, i, heap_size);
    }
    void heap_sort(vector<int> &a){
        build_heap(a);
        int heap_size = a.size();
        while(heap_size > 1){
            swap(a[heap_size-1], a[0]);
            heap_size--;
            max_heapify(a, 0, heap_size);
        }
    }
    
    //希尔排序
    void shell_sort(vector<int> &arr){
        int len = arr.size();
        int gap;
        int i,j;
        for(gap = len/2; gap>0; gap /= 2)
            for(i=gap; i<len; i++){
                int temp = arr[i];
                for(j=i-gap; j>=0 && arr[j] > temp; j -= gap)
                    arr[j+gap] = arr[j];
                arr[j+gap] = temp;
            }
    }
    展开全文
  • 快速排序算法c++实现

    2011-10-16 00:30:54
    快速排序算法c++实现,快速实现插入排序十万个数(调用)。可以改成输入。并附加了程序运行计时,用于测试时间复杂度,可以移除。绝对能用
  • 插入排序算法c++实现

    2011-10-15 16:55:22
    插入排序算法c++实现,程序实现插入排序十万个数(调用)。可以改成输入。并附加了程序运行计时,用于测试时间复杂度,可以移除。绝对能用
  • 排序算法 C++实现

    2010-08-11 14:25:00
    冒泡排序 插入排序 merge sort(合并排序) 快速排序
    展开全文
  • 十大排序算法c++实现,建议结合下面这篇文章看 ...
  • 【数据结构】十大排序算法C++实现

    千次阅读 多人点赞 2021-05-12 18:41:23
    参考 数据结构十大排序算法讲解:算法原理和LeetCode代码实现(C++,java) 【数据结构】十大排序算法—— C++实现全> 十大经典排序算法C++实现
  • 常见排序算法C++实现

    2017-01-23 14:33:33
    C++实现了常见几种排序算法:归并排序,快速排序,希尔排序,插入排序,选择排序
  • 各种排序算法 C++实现

    2015-07-13 22:14:13
    本文件为基于vs2010平台的使用C++语言的各种排序算法c++实现。其中有计数排序 基排序 快排 归并排序 堆排序。代码精心总结,有详细的注释,结构清晰,对初学算法的人有很大帮助。
  • 快速排序算法c++实现算法思想:首先任意选取一个数据作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。快速排序算法的核心算法是分区操作,即如何调整...
  • 考研排序算法C++实现

    2020-11-02 16:17:27
    关键地方加了注释,如果有没看明白的地方欢迎加我
  • 六大排序算法C++实现

    2016-03-19 20:08:16
    六大排序算法C++实现 六大排序包括,冒泡(附加冒泡排序的改进)、选择、插入、堆排序、快排、归并排序,这些排序的定义和优劣这里不赘述,大家可自行查阅其他资料或博客,这里给出他们的C++实现 1、冒泡排序/*普通...
  • 常用排序算法C++实现(堆排序,快速排序,归并排序,基数排序)
  • 八大排序算法c++实现

    2019-04-22 12:02:06
    复习用整理代码。包括直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序
  • 常用排序算法C++实现

    2010-11-07 21:00:22
    常用8个排序算法C++实现,经测试全部可以运行通过,分别是插入排序,选择排序,冒泡排序,二分插入排序,希尔排序,快速排序,堆排序,归并排序
  • 七大排序算法C++实现(代码分享)

    千次阅读 2016-05-28 21:12:38
    七大排序算法C++实现(代码分享)  By qianghaohao(Xqiang)  #include #include #include #include using namespace std; //****************************************
  • 快速排序算法 c++实现

    2021-03-28 11:54:38
    tip:递归不要陷进去了,一定要找其中的关系,否则很难理解递归。... //对右边进行排序 } } int main() { vector a = { 3,4,23,1,7 }; sort(a, 0, 4); for (int i = 0;i != a.size();++i) { cout [i]; } return 0; }
  • 快速排序算法C++实现

    2020-04-24 14:04:06
    快排算法 代码 代码参考链接为https://blog.csdn.net/qq_28584889/article/details/88136498 感谢 结果为升序(从小到大) void quickSort(int left, int right, vector<int>& arr) { if(left >= ...
  • 快速排序算法 C++实现

    2018-07-03 12:25:50
    快速排序算法 快排是对冒泡排序的改进。时间复杂度为O(nlog2n)。 改进点:在冒泡排序中是对相邻位置上的比较和移动,每次交换只能前移或者后移一个单位;快排中,记录的比较和移动是从两端向中间进行,关键码较大...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,397
精华内容 2,558
关键字:

排序算法c++实现

c++ 订阅