精华内容
下载资源
问答
  • 算法笔记(二)线性排序一百万数据量如何进行快速排序
    千次阅读
    2019-10-30 23:29:46

    线性排序:时间复杂度为 O(n)是线性的 不涉及元素之间的比较操作(但是对排序之间的数据比较苛刻)

    常见的三种:
    1.桶排序:将要排序的数据分到几个有序的桶里,然后由对桶内的数据再单独进行排序,排序完,再将每个桶里的数据按照顺序依次取出,最后组成的数据就是有序的了。可对数据范围比较大的数据依次划分范围桶(比较适合用于外部排序 内存有限不将数一次性加载到内存中 先将数据存储到外部磁盘中)

    2.计数排序:其实可以算是桶排序的一种特殊情况(再将桶的划分进行细化到 1 位)常见如:计算高考 500万考生的成绩进行排序 由于其范围是比较小的 满分是 750分 最低分是 0 分 我们可以将其划分为 751 个桶,将考生扫描一遍依次放入桶内 并进行计数,最后桶内数据依次取出 通常用于 数据量大 但数据范围比较小的情况

    3.基数排序:
    思想:如果一个数据的高位大于另一个数据,那么可以忽略地位认为这个数更大将一系列数据
    具体实现:每个按照位数进行划分 再进行每位的排序 通常用于 数据量大 位数也较长 不好进行桶位的划分
    例如:对全国手机用户手机号的排序 (位数不一致也可以进行补 0 的操作使得数据位数一致)

    更多相关内容
  • 百万数据进行查询与排序

    千次阅读 2017-08-11 21:57:15
    在网上找了堆,有一下几大排序算法如:快速排序,归并排序,堆排序,百万数据查询 。 那什么是快速排序:  1. 快速排序算法是种不稳定的排序算法。其时间复杂度为O(nlogn),最坏复杂度为O(n^2);快排的平均...

    百万数据进行查询与排序!

    在网上找了一堆,有一下几大排序算法如:快速排序,归并排序,堆排序,百万数据查询 。

    那什么是快速排序:

         1.  快速排序算法是一种不稳定的排序算法。其时间复杂度为O(nlogn),最坏复杂度为O(n^2);快排的平均空间复杂度为O(logn),关于空间界的论断来自于《编程珠玑第2版》第113页。但是其最坏空间复杂度为O(n)。

           快速排序的基本思想是使用两个指针来遍历待排序的数组,根据两个指针遍历的方向可以分为两类:第一,两个指针从待排序数组的同一个方向遍历。第二,两个指针分别从带排序数组的两端进行遍历。下列的几种算法都可以归为这两类中的某类。

            下图给出的是两个指针从同一方向遍历时的状态。下图的第一个图给出的是循环过程中的状态,在循环中,low指向的是小于枢纽的那部分元素的最右端,high在未排序的部分遍历。循环直到high指针到达right的位置(数组的最右端),如下图第二个图所示。此时数组除了枢纽pivot被划分为两部分:小于pivot的和大于等于pivot的。然后将low和枢纽元素交换就可以得到本次排序的第一趟结果,如下图的第三幅图所示。

             

               当从两个方向分别遍历数组时,下图是遍历的循环过程状态。循环时,low向右移动,high向左移动。


    那什么是归并排序:

               2.归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

    分而治之

       可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。阶段可以理解为就是递归拆分子序列的过程,递归深度为log2n。

    合并相邻有序子序列

      再来看看阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。

    代码实现

    复制代码
    package sortdemo;
    
    import java.util.Arrays;
    
    /**
     * Created by chengxiao on 2016/12/8.
     */
    public class MergeSort {
        public static void main(String []args){
            int []arr = {9,8,7,6,5,4,3,2,1};
            sort(arr);
            System.out.println(Arrays.toString(arr));
        }
        public static void sort(int []arr){
            int []temp = new int[arr.length];//在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
            sort(arr,0,arr.length-1,temp);
        }
        private static void sort(int[] arr,int left,int right,int []temp){
            if(left<right){
                int mid = (left+right)/2;
                sort(arr,left,mid,temp);//左边归并排序,使得左子序列有序
                sort(arr,mid+1,right,temp);//右边归并排序,使得右子序列有序
                merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
            }
        }
        private static void merge(int[] arr,int left,int mid,int right,int[] temp){
            int i = left;//左序列指针
            int j = mid+1;//右序列指针
            int t = 0;//临时数组指针
            while (i<=mid && j<=right){
                if(arr[i]<=arr[j]){
                    temp[t++] = arr[i++];
                }else {
                    temp[t++] = arr[j++];
                }
            }
            while(i<=mid){//将左边剩余元素填充进temp中
                temp[t++] = arr[i++];
            }
            while(j<=right){//将右序列剩余元素填充进temp中
                temp[t++] = arr[j++];
            }
            t = 0;
            //将temp中的元素全部拷贝到原数组中
            while(left <= right){
                arr[left++] = temp[t++];
            }
        }
    }
    复制代码

    执行结果

    [1, 2, 3, 4, 5, 6, 7, 8, 9]

    最后

      归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法,就是归并排序的优化版本。从上文的图中可看出,每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且,归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。


    那什么是堆排序:

              3.堆排序是一种选择排序,其时间复杂度为O(nlogn)。

    堆的定义

      n个元素的序列{k1,k2,…,kn}当且仅当满足下列关系之一时,称之为堆。

      情形1:ki <= k2i 且ki <= k2i+1 最小化堆小顶堆

      情形2:ki >= k2i 且ki >= k2i+1最大化堆大顶堆

      其中i=1,2,…,n/2向下取整;

         

                     

     

      若将和此序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值

      由此,若序列{k1,k2,…,kn}是堆,则堆顶元素(或完全二叉树的根)必为序列中n个元素的最小值(或最大值)。

      例如,下列两个序列为堆,对应的完全二叉树如图:

      

     

      若在输出堆顶的最小值之后,使得剩余n-1个元素的序列重又建成一个堆,则得到n个元素的次小值。如此反复执行,便能得到一个有序序列,这个过程称之为堆排序

      堆排序(Heap Sort)只需要一个记录元素大小的辅助空间(供交换用),每个待排序的记录仅占有一个存储空间。

     

    堆的存储

      一般用数组来表示堆,若根结点存在序号0处, i结点的父结点下标就为(i-1)/2。i结点的左右子结点下标分别为2*i+12*i+2

      (注:如果根结点是从1开始,则左右孩子结点分别是2i和2i+1。)

      如第0个结点左右子结点下标分别为1和2。

      如最大化堆如下:

       

     

      左图为其存储结构,右图为其逻辑结构。

    堆排序的实现

      实现堆排序需要解决两个问题:

        1.如何由一个无序序列建成一个堆?

        2.如何在输出堆顶元素之后,调整剩余元素成为一个新的堆?

     

      先考虑第二个问题,一般在输出堆顶元素之后,视为将这个元素排除,然后用表中最后一个元素填补它的位置,自上向下进行调整:首先将堆顶元素和它的左右子树的根结点进行比较,把最小的元素交换到堆顶;然后顺着被破坏的路径一路调整下去,直至叶子结点,就得到新的堆。

      我们称这个自堆顶至叶子的调整过程为“筛选”。

      从无序序列建立堆的过程就是一个反复“筛选”的过程。

    构造初始堆

      初始化堆的时候是对所有的非叶子结点进行筛选。

      最后一个非终端元素的下标是[n/2]向下取整,所以筛选只需要从第[n/2]向下取整个元素开始,从后往前进行调整。

      比如,给定一个数组,首先根据该数组元素构造一个完全二叉树。

      然后从最后一个非叶子结点开始,每次都是从父结点、左孩子、右孩子中进行比较交换,交换可能会引起孩子结点不满足堆的性质,所以每次交换之后需要重新对被交换的孩子结点进行调整。

    进行堆排序

      有了初始堆之后就可以进行排序了。

      堆排序是一种选择排序。建立的初始堆为初始的无序区。

      排序开始,首先输出堆顶元素(因为它是最值),将堆顶元素和最后一个元素交换,这样,第n个位置(即最后一个位置)作为有序区,前n-1个位置仍是无序区,对无序区进行调整,得到堆之后,再交换堆顶和最后一个元素,这样有序区长度变为2。。。

      不断进行此操作,将剩下的元素重新调整为堆,然后输出堆顶元素到有序区。每次交换都导致无序区-1,有序区+1。不断重复此过程直到有序区长度增长为n-1,排序完成。

    堆排序实例

       首先,建立初始的堆结构如图:

      

      然后,交换堆顶的元素和最后一个元素,此时最后一个位置作为有序区(有序区显示为黄色),然后进行其他无序区的堆调整,重新得到大顶堆后,交换堆顶和倒数第二个元素的位置……

      

      重复此过程:

      

     

      最后,有序区扩展完成即排序完成:

      

     

      由排序过程可见,若想得到升序,则建立大顶堆,若想得到降序,则建立小顶堆

    代码

      假设排列的元素为整型,且元素的关键字为其本身。

      因为要进行升序排列,所以用大顶堆。

      根结点从0开始,所以i结点的左右孩子结点的下标为2i+1和2i+2。

    堆排序分析

      堆排序方法对记录数较少的文件并不值得提倡,但对n较大的文件还是很有效的。因为其运行时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。

      堆排序在最坏的情况下,其时间复杂度也为O(nlogn)。相对于快速排序来说,这是堆排序的最大优点。此外,堆排序仅需一个记录大小的供交换用的辅助存储空间。

    查百万数据查询几种方法:

    第一种:

    经过测试 在USERID上建立聚集索引 是这样
    DBCC DROPCLEANBUFFERS  
    DBCC FREEPROCCACHE
    SET  STATISTICS  IO  ON
    SET  STATISTICS  TIME  ON
    select  from  csdn  where  userid= 'yudannm1'
    --set statistics time off
    /*
      SQL Server 执行时间:
        CPU 时间 = 0 毫秒,占用时间 = 0 毫秒。
    SQL Server 分析和编译时间: 
        CPU 时间 = 0 毫秒,占用时间 = 0 毫秒。
    userid                                             password                                                                                     email
    ------------------------------------------------------------------------------------------------------------------------------------------------------
    yudannm1                                           yudannm11                                                                                             490219906@qq.com
     
    (1 行受影响)
     
    表  'csdn' 。扫描计数 1,逻辑读取 4 次,物理读取 4 次,预读 0 次,lob 逻辑读取 0 次,lob 物理读取 0 次,lob 预读 0 次。
     
      SQL Server 执行时间:
        CPU 时间 = 16 毫秒,占用时间 = 28 毫秒。*/

    第二种:

    几种方法, 供你参考:
    1.  设置行版本控制级别, 防止堵塞;

    1
    2
    3
    SET  TRANSACTION  ISOLATION  LEVEL  READ  UNCOMMITTED  ;
    SELECT  FROM  TABLE_NAME ;
    COMMIT  ;
    2.  如果介绍并不重要, 只是偶尔看看, 建议把把介绍分到另外一个新表, 需要时再连接;

    第三种:

    使用索引引擎。

    第四种:

    用算法与数据库结合。


    展开全文
  • 冒泡排序(时间复杂度N2,空间复杂度1) 依次比较数组相邻两元素,将最大或最小元素放到后面,慢慢“浮”到数列的最后。 选择排序(时间复杂度N2,空间...将数组分为有序和无序两部分,默认数组左变第一个元素是...
    1. 冒泡排序(时间复杂度N2,空间复杂度1)
      依次比较数组相邻两个元素,将最大或最小元素放到后面,慢慢“浮”到数列的最后。
    2. 选择排序(时间复杂度N2,空间复杂度1)
      首先找到数组最小元素,将它和数组的第一个元素交换位置。再次,在剩下的元素中找到最小的元素,将它与数组第二个元素交换,如此往复。
    3. 插入排序(时间复杂度介于N和N2之间,空间复杂度1)
    4. 将数组分为有序和无序两个部分,默认数组左变第一个元素是有序的,依次遍历数组第二个元素到最后,与数组左变有序序列比较。如果小于左变有序序列则交换位置。
    5. 希尔排序(时间复杂度NlogN,空间复杂度1)
      分组+插入排序。插入排序只能交换相邻的元素,元素只能一点一点从数组的一端移动到另一端。希尔排序的思想是使数组中任意间隔为gap的数组都是有序的。经验公式:gap=gap/3+1,如果有12个元素,那么同一组元素相邻元素间隔4,下一次分组间隔2,最后一次间隔1。
    6. 归并排序(时间复杂度NlogN,空间复杂度N(递归临时变量))
      将两个有序数组归并到第三个数组中,递归在发生在处理数组之后。
    7. 快速排序(时间复杂度NlogN,空间复杂度lgN))
      与归并一样,都是利用分治的排序算法。将数组分成两个子数组,将两部分独立排序,递归发生在处理数组之前。不需要额外的内存空间存储一个临时数组。
    8. 堆排序(时间复杂度NlogN,空间复杂度1)
      利用堆(一种特殊的完全二叉树)而设计的一种排序算法。如果是正序排序,先构建一个最大堆,交换a[1]和a[n],此时a[n]就是数组中最大元素。n–,a[1]向下调整保持最大堆特性,进行下一次交换。
    9. 桶排序(时间复杂度lg(M+N),空间复杂度N)
      构建一个临时数组book,长度为要排序数组的最大值。遍历一次数组a,记录a[i]的值的次数:book[a[i]]++j.最后遍历一遍数组book,将i值和出现的数次写到数组a中。

    这里是引用

    #include<iostream>
    #include<time.h>
    #include <sys/timeb.h>
    using namespace std;
    //效率测试
    #define NUMBER 1000000
    long long getSystemTime()
    {
    	struct timeb t;
    	ftime(&t);
    	return 1000 * t.time + t.millitm;
    }
    
    
     void bucketSort(int *a,int *book, int len)
    {
    	 for (int i = 0; i < len; i++)
    	 {
    		 int tem = a[i];
    		 book[tem]++;
    	 }
    	 int k = 0;
    	 for (int i = 0; i < NUMBER; i++)
    	 {
    		 int ncount = book[i];
    		 for (int j = 0; j < ncount; j++)
    		 {
    			 a[k++] = i;
    		 }
    	 }
    }
    
     //-----------------三向切分的快速排序 ---------------------
    void quick3WaySort(int *a, int left, int right)
    {
    	if (left > right) return;
    	int lt = left;
    	int i = left + 1;
    	int gt = right;
    	int tem = a[left];
    	while (i <= gt)
    	{
    		if (a[i] < tem)  //小于切分元素的放在lt左边,lt和i整体右移
    		{
    			//exchange(a, lt++, i++);
    			int tmp = a[i];
    			a[i] = a[lt];
    			a[lt] = tmp;
    			lt++; i++;
    		}
    		else if (a[i] > tem)//大于切分元素的放在gt右边,因此gt左移
    		{
    			//exchange(a, i, gt--);
    			int tmp = a[i];
    			a[i] = a[gt];
    			a[gt] = tmp;
    			gt--;
    		}
    		else
    			i++;
    	}
    	quick3WaySort(a,left,lt-1);
    	quick3WaySort(a, gt+1, right);
    }
    
    
    #if 0
    void quickSort(int *a, int left, int right)
    {
    	if (left > right) return;
    	int i = left;
    	int j = right;
    	int tem = a[left];
    	while (i != j) 
    	{
    		while (a[j]>tem && i<j)
    			j--;
    		while (a[i] <= tem &&i<j)
    			i++;
    		if (i < j)
    		{
    			int t = a[j];
    			a[j] = a[i];
    			a[i] = t;
    		}
    	}
    
    	a[left] = a[i];
    	a[i] = tem;
    
    	quickSort(a, left, i - 1);
    	quickSort(a, i+1, right);
    	return;
    }
    #endif
    //---------------堆排序--------------------
    void shiftDown(int *a,int len,int i)
    {
    	int index, flag = 0;
    	//----结点有左孩子-----
    	while (i * 2 <= len && flag == 0)
    	{
    		if (a[i] < a[i * 2])
    			index = i * 2;
    		else
    			index = i;
    		//----结点有左孩子-----
    		if (i * 2 + 1 <= len)
    		{
    			if (a[index] < a[i * 2 + 1])
    				index = i * 2 + 1;
    		}
    		if (index != i)
    		{
    			//---交换i节点与子节点,更新编号为下一次向下调整准备
    			int tem = a[i];
    			a[i] = a[index];
    			a[index] = tem;
    			i = index;  
    		}
    		else
    		{
    			flag = 1;
    		}
    	}
    }
    
    
    void heapSort(int *a, int len)
    {
    	//-------------建最大堆----------------
    	for (int i = len / 2; i >= 1; i--)
    	{
    		shiftDown(a,len,i);
    	}
    	//--------------排序-------------------
    	while (len>1)
    	{
    		int tem = a[len];
    		a[len] = a[1];
    		a[1] = tem;
    		len--;
    		shiftDown(a,len,1);
    	}
    }
    
    
    //-------------------归并排序-------------------------
    void merge(int *a, int first, int mid, int last, int *temp)
    {
    	int i = first;      // 第1个有序序列的开始下标
    	int j = mid + 1;    // 第2个有序序列的开始下标
    	int len = 0;
    	// 合并两个有序序列
    	while (i <= mid && j <= last)
    	{
    		if (a[i] < a[j])
    		{
    			// 找二者中比较小的数
    			temp[len] = a[i];
    			i++;
    		}
    		else
    		{
    			temp[len] = a[j];
    			j++;
    		}
    		len++;
    	}
    	while (i <= mid)
    	{
    		temp[len] = a[i];
    		i++;
    		len++;
    	}
    	while (j <= last)
    	{
    		temp[len] = a[j];
    		j++;
    		len++;
    	}
    	// 找到原来的第一个有序序列的开始位置覆盖无序序列
    	for (int k = 0; k < len; k++)
    	{
    		a[first+k] = temp[k];
    	}
    }
    
    void mergeSort(int *a, int first, int last, int *temp)
    {
    	if (first == last)
    		return;
    	int mid =  first+ (last - first) / 2; //防止first+last溢出
    	mergeSort(a, first, mid, temp);
    	mergeSort(a, mid+1, last, temp);
    	merge(a, first, mid, last, temp);
    }
    
    //-------------------希尔排序-------------------
    void shellSort(int *a, int len)
    {
    	int gap = len;
    	int index, tem;
    	while (gap > 1)
    	{
    		gap = gap / 3 + 1;
    		// =======分组, 对每一组, 进行插入排序
    		for (int i = 0; i < gap; i++)
    		{
    			//----插入排序----------
    			for (int j = i + gap; j < len; j += gap)
    			{
    				index=j;  
    				tem=a[j];
    				for (int k = j; k > i; k -= gap)
    				{
    					if (tem < a[k - gap])
    					{
    						a[k] = a[k - gap];
    						index = k - gap;
    					}
    					else
    					{
    						break;
    					}
    				}
    				a[index] = tem;
    			}
    		}
    	}
    }
    
    
    //--------------------插入排序---------------------
    void insertSort(int *a, int len)
    {
    	int index;
    	int tem;
    	// 遍历无序序列
    	for (int i = 1; i < len; i++)
    	{
    		index = i;  //存储当前基准数位置
    		tem = a[i];
    		// 遍历有序序列
    		for (int j = i; j >0; j--)
    		{
    
    			if (tem < a[j - 1])  //找到比基准数大的位置,则将有序序列后移,并记录有序序列位置
    			{
    				a[j] = a[j - 1];
    				index = j - 1;
    			}
    			else
    			{
    				break;
    			}
    		}
    		a[index] = tem; //将基准数填入
    	}
    }
    
    //--------------选择排序---------------
    
    void selectSort(int *a, int len)
    {
    	for (int i = 0; i < len; i++)
    	{
    		int min = i;//基准书位置
    		for (int j = i + 1; j < len; j++)
    		{
    			if (a[min] > a[j])
    				min = j; //没遍历一次,找到最小值的序号
    		}
    		
    		int tem = a[min];  //交换基准数和最小元素
    		a[min] = a[i];
    		a[i] = tem;
    	}
    }
    
    //----------------冒泡排序------------------
    void bubbleSort(int *a, int len)
    {
    	int flag = 0;//0表示没有排序好,1表示排序好了
    	for (int i = 0; i < len && flag == 0; i++)
    	{
    		//每进行一次冒泡,首先默认已经排好
    		flag = 1;
    		for (int j = 1; j < len - i; j++)
    		{
    			if (a[j] < a[j - 1])
    			{
    				int tem = a[j - 1];
    				a[j - 1] = a[j];
    				a[j] = tem;
    				flag = 0;
    			}
    
    		}
    	}
    }
    
    int main()
    {
    	long long timeStart, timeEnd, timeUse;
    	srand((unsigned)time(NULL));
    
    	int(*array)[NUMBER] = new int[7][NUMBER];
    	int *arrayHeap = new int[NUMBER+1];
    
    	//-----归并和桶排序额外的内存---
    	int *mergeArray = new int[NUMBER];
    	int *bucketArrayBook = new int[NUMBER]();
    	for (int i = 0; i < NUMBER; ++i)
    	{
    		//生成一个小于len的随机数
    		int number = rand() % NUMBER;
    		for (int j = 0; j < 7; ++j)
    		{
    			array[j][i] = number;
    		}
    		arrayHeap[i+1] = number;
    	}
    
    
    	cout << "对第" << NUMBER << "个数进行排序" << endl;
    	timeStart = getSystemTime();
    	bucketSort(array[0], bucketArrayBook, NUMBER);
    	timeEnd = getSystemTime();
    	timeUse = timeEnd - timeStart;
    	cout << "bucketSort     耗时:" << timeUse << "ms" << endl;;
    
    	timeStart = getSystemTime();
    	quick3WaySort(array[1], 0, NUMBER-1);
    	timeEnd = getSystemTime();
    	timeUse = timeEnd - timeStart;
    	cout << "quick3WaySort  耗时:" << timeUse << "ms" << endl;;
    
    	timeStart = getSystemTime();
    	heapSort(arrayHeap, NUMBER);
    	timeEnd = getSystemTime();
    	timeUse = timeEnd - timeStart;
    	cout << "heapSort       耗时:" << timeUse << "ms" << endl;;
    
    	timeStart = getSystemTime();
    	mergeSort(array[2],0, NUMBER-1, mergeArray);
    	timeEnd = getSystemTime();
    	timeUse = timeEnd - timeStart;
    	cout << "mergeSort      耗时:" << timeUse << "ms" << endl;;
    
    	timeStart = getSystemTime();
    	shellSort(array[3], NUMBER);
    	timeEnd = getSystemTime();
    	timeUse = timeEnd - timeStart;
    	cout << "shellSort      耗时:" << timeUse << "ms" << endl;;
    
    	timeStart = getSystemTime();
    	insertSort(array[4], NUMBER);
    	timeEnd = getSystemTime();
    	timeUse = timeEnd - timeStart;
    	cout << "insertSort     耗时:" << timeUse << "ms" << endl;;
    
    	timeStart = getSystemTime();
    	selectSort(array[5], NUMBER);
    	timeEnd = getSystemTime();
    	timeUse = timeEnd - timeStart;
    	cout << "selectSort     耗时:" << timeUse << "ms" << endl;;
    
    	timeStart = getSystemTime();
    	bubbleSort(array[6], NUMBER);
    	timeEnd = getSystemTime();
    	timeUse = timeEnd - timeStart;
    	cout << "bubbleSort     耗时:" << timeUse << "ms" << endl;
    
    	delete []array;
    	delete arrayHeap;
    	delete mergeArray;
    	delete bucketArrayBook;
    }
    

    在这里插入图片描述
    在这里插入图片描述
    总结:
    1.在这8中排序算法当中,桶排序是最快的,冒泡排序最慢。
    但是,桶排序要求构建一个待排序最大元素的数组,往往排序的时候我们并不能确定最大元素的值,另一方面和并归排序一样,当数组很大的时候,也要考虑额外的内存分配问题。
    2.在数组非常长的排序,各种排序算法中,三向切分快速排序是最快的(较快速排序提升了20%到30%)。但是,需要考虑递归产生临时是否会导致栈溢出的问题。堆排序时间复杂度ONlogN,空间复杂度1,并且对已经排序好的数组插入一个元素的时候,堆是一种优先队列的时间,查找和插入的时间复杂度较优。
    3.对于小数组,快速排序比插入排序慢。因此在设计排序的时候可以考虑通过判断长度来切换排序算法。

    展开全文
  • 最快的排序算法是时间复杂度是 O(nlogn)十数据量的复杂度,也就是进行 100000*log(100000) = 17次运算。以现在计算机的运算速度(单位是每秒百万条指令),如果你不是做一些有时间限制的竞赛(AC...

    首答,欢迎追问与提意见,先说我的思路,用桶,以空间换时间的方式得到最快速度的答案,C代码在最下面,已测试。

    测试结果:

    3bc48f9a6280545b017a6789476895f5.png

    思考了一会,按照常规方法走,如果没有特殊要求,用排序是可以的。最快的排序算法是时间复杂度是 O(nlogn)

    十万的数据量的复杂度,也就是进行 100000*log(100000) = 17万次运算。

    以现在计算机的运算速度(单位是每秒百万条指令),如果你不是做一些有时间限制的竞赛(ACM)的话,是完全可以的。

    但这道题如果放在ACM竞赛中,如果用排序方法去做应该是铁铁的超时了。

    于是我用桶(C语言桶的概念不懂请百度)做了一个以空间换时间的折中算法,时间复杂度是O(n),也就是10万次运算。空间复杂度取决于最大数字。如果最大数字是10万,就要开辟10万的数组空间,如果最大数字是20万,就要开辟20万的数组空间。如果最大数字是一百万,就要开辟一百万数组大小的空间,C语言不支持开辟这么多连续的内存空间,如果你真有这个问题,可以在segmentfault上提一个新问题,或者在答案下追问。

    具体思路:

    结果分为两个堆:0堆和1堆。

    用桶存放所有元素的出现次数,对桶进行遍历,记录数组中所有的元素出现次数之和为count,当count>=N/2时(N在这里为10万),停止遍历。

    [1] 这时遍历过的就是在左边堆的了。没遍历过的就是在右边堆里的了。

    比如

    3 2 1 4 5 3

    排序后 1 2 3 3 4 5

    桶(记为b)的状态: b[0]=0, b[1]=1, b[2]=1, b[3]=2, b[4]=1, b[5]=1

    当遍历到b[3]的时候,count为4,已经大于3了(元素个数/2)。这时候记录一下中间数的位置

    然后根据上面思路[1] 就很容易得出1 2 3 3 都是在左边堆的,

    4 5 都是在右边堆的。

    这时候出现了一个bug,有两个3,其中1个3应该在右边。

    这个问题很好解决,上例中,count在停止记数的时候为4,4与3相比较多了1,证明多加了一个。所以要把最后一个移到右边堆。

    C语言代码

    把N改成10万,记得把printf该关的关掉。

    #include

    #include

    #define N 19

    #define MAX 32767

    int main()

    {

    int a[N] = {0}, b[MAX] = {0};

    int count = 0, position = -1;

    printf("the random data is \n\n");

    for(int i=0; i

    {

    a[i] = (int)(rand() % MAX); //产生MAX以下的随机数

    b[a[i]]++; //统计每个数字出现的次数

    printf("%5d ",a[i]);

    }

    for(int i=0; i

    {

    if(b[i] == 0)

    continue;

    count += b[i]; //统计从小到大所有的数字出现的次数

    if(count >= N/2)

    {

    position = i; //找到分界点时记录位置

    break;

    }

    }

    printf("\n-----------------\n\nthe result is\n\n");

    int temp = 0;

    for(int i=0; i

    {

    if(a[i] < position)

    printf(" left ");

    else if(a[i] == position)

    {

    if(++temp <= b[a[i]]-(count-N/2)) //左右分界点的值出现多次的时候,控制一下。

    printf(" left ");

    else

    printf("right ");

    }

    else

    printf("right ");

    }

    printf("\n\n>>>>>> Middle is %5d\n",position);

    return 0;

    }

    PS:其实我感觉应该有不浪费空间又可以节省时间的方法,但想了半天没想出来,如果有更好的答案望分享。

    我是学Java的,也专门学习过一些算法知识,正在往全栈方面发展。有兴趣可以加个兴趣群一起交流,群号374660776

    展开全文
  • 、首先我们直接与现有的排序算法:快速排序、C++库里的Sort、计数法桶排序进行速度对比 1、如图所示,这就是测试所需要的数据和方法。 2、用1000升序数据进行排序,小于几毫秒我就不写了,直接写毫秒 C++...
  • 我们有10GB的订单数据,我们希望按订单金额(假设金额都是正整数)进行排序,但是我们的内存有限,只有几MB,没办法次性把10GB的数据都加 载到内存中。这时候该怎么办呢? 桶排序(Bucket sort) 桶排序,...
  • Java ArrayList实现快速排序(D&C)

    千次阅读 2020-04-15 01:57:13
    分而治之的方法,分解列表直到满足基线条件,默认选取的基准值为当前列表的第一个元素。ArrayList相较于Int[]更容易实现,不过借助了ArrayList的方法还是有取巧的地方。 import java.util.ArrayList; import java...
  • 1. 算法如下:根据快速排序划分的思想 (1) 递归所有数据分成[a,b)b(b,d]两区间,(b,d]区间内的数都是大于[a,b)区间内的数 (2) (b,d]重复(1)操作,直到最右边的区间数小于100。注意[a,b)区间不用划分...
  • 2. 想要在生成随机数之后将随机数保存在一个TXT文件中,在将数据全部排序之后将排序后的数据也保存在同一个TXT文件中,但是我写出来的代码总是有问题,TXT中保存的都是乱码。求教大神们帮我改改我的程序!万分感谢!...
  • java 怎么将List里面数据排序

    千次阅读 2021-02-12 12:24:13
    ArrayList底层是用一个长度为62616964757a686964616fe4b893e5b19e3133333264316410的Object数组实现,不管添加进去什么类型的数据,都会转换成Object对象,除非你用很早以前的JDK版本。这样就好理解了,像你写的程序...
  • 本文是学习算法的笔记,《数据结构...这三算法不涉及元素之间的比较操作,是非基于比较的排序算法。 先给出一道思考题:**如何根据年龄给100用户排序?**你可能会说,用上一节讲的归并、快排就可以搞定啊!是的...
  • 算法给小码农冒泡排序铭纹,快速排序四极

    千次阅读 多人点赞 2021-11-27 21:19:49
    很简单的一个排序==完整冒泡排序代码快速排序(无敌的排序)将区间按照基准值划分为左右两半部分的常见方式有:1.hoare版本==(发明快排的人用的方法)==最左边做key最右边做key测性能选1000 千选10000 一万选...
  • 在java开发中有时候我们需要List集合中的元素按照一定的规则进行排序,比如说有Person的集合,我们要根据Person的age属性进行排序输出,这就需要用到Java中提供的集合进行操作的工具类Collections,其中的sort...
  • 冒泡排序快速排序希尔排序堆排序归并排序以下内容主要包括算法实现。补充内容概念内容:#include&lt;iostream&gt;:主要功能是处理输入输出流。(具体参考:...
  • 数据结构和算法之排序总结

    千次阅读 多人点赞 2021-11-03 19:35:22
    、排序的概念及应用 ???? 排序的概念 ...2、快速排序 ???? 归并排序 ???? 非比较排序 1、计数排序 2、基数排序 ???? 文件排序 (拓展) ???? 性能测试 三、排序算法复杂度及稳定性分析 四、概念选择题
  • 排序算法准备算法模板冒泡排序(Bubble Sort)定义执行流程代码实现选择排序(...快速排序(Quick Sort)定义执行流程代码实现计数排序(Counting Sort)定义执行流程代码实现基数排序(Radix Sort)定义执行流程代码实现桶排
  • 输入n组测试数据,从小到大排序. 输入 输出 样例输入 2 3 3 6 5 4 8 5 9 7 样例输出 3 6 5 5 7 8 9 提示 (1 <= n <= 100000) #include <iostream> using namespace std; int a...
  • 点击上方“Python全家桶”,“星标”或"置顶"关键时刻,第时间送达链接:www.cnblogs.com/geningchao/p/6649907.html方法...N适应场景:适用于数据量较少的情况(元组/千级)原因/缺点:全表扫描,速度会很慢 且 有的...
  • 数据智能时代,企业而言,“数据驱动业务”或者“数据即是业务”的理念逐渐成为业界的种共识。然而,数据孤岛、数据标准不统一等问题在一定程度上阻碍了数据资产价值的最大化体现。推作为专业的数据智能服务...
  • 数据量太多,一个节点可能有数子节点,显示会非常卡(一般来说,最多显示几百个才能保证性能,超过 1000 很容易卡); 当多展开几子节点后,很难找到自己需要的那个子节点; 即使增加过滤/搜索功能,也不太方便...
  • 10亿数据中取最大的100个数据

    千次阅读 2016-04-18 22:11:22
    思路1:根据快速排序划分的思想 (1)递归所有数据分成[a,b)b(b,d]两区间,(b,d]区间内的数都是大于[a,b)区间内的数 (2)(b,d]重复(1)操作,直到最右边的区间数小于100。注意[a,b)区间不用划分 (3...
  • 快速排序的几种常见实现及其性能对比

    万次阅读 多人点赞 2014-12-22 19:11:54
    假设待排序的数组为a[],快速排序算法最常见的做法是将第一个元素设置为枢纽元。设置两指针low和high,它们分别指向待排序的数组的低和高位: (1)high向左移动找小于枢纽的元素,找到后(找到的是a[high]
  • 数据结构之你没见过的排序算法!

    千次阅读 2020-12-16 08:50:03
    现在随着业务的积累,自己在这行业也懂了一点皮毛,特地总结一下自己学过的排序算法,以及排序的性能,参考了许许多多的资料 ,明白了排序的的方式千奇百怪,我们只能选择最符合我们业务的哪种, 好了废话不多说...
  • 海量数据找到最大的100个数据

    千次阅读 2019-03-07 16:43:11
    如果是 int 型数据,int型数组占4字节的内存,1亿int型数据就得占用近400M的内存,计算机性能差的话很难次性读入然后排序。所以一般的靠排序来做这道题是很尴尬的。 这里用最小堆来解决,上篇讲了大顶堆的原理...
  • 数据结构中各种排序算法比较

    千次阅读 2017-11-08 16:02:49
    快速排序一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序的就地版本。快 速排序可以由下面四步组成。     ( 1 )   如果不多于 1 个数据,直接返回。   ( 2 )   一般选择序列最...
  • 排序算法07:三向快速排序

    千次阅读 2017-04-30 23:21:11
    算法介绍  在上篇排序算法06:快速排序中,可以知道,快速排序不停的递归切分数组。在有大量的重复元素情况下,这样的切分存在巨大的改进空间。三向切分的快速排序就是为了提升在有大量重复元素情况下快速排序的...
  • 十大排序算法就看这里

    千次阅读 2020-06-17 22:12:43
    十大经典排序算法:冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、基数排序、堆排序、桶排序、计数排序原理及代码实现
  • Bigtable:一个分布式的结构化数据存储系统 本文的英文原文为Google在2006年发布的Google Bigtable paper 本文的翻译版本由Alex完成,原文地址为: http://blademaster.ixiezi.com/ 这是我很长时间以来...
  • 【空间复杂度】O(1) 堆排序所用的堆(二叉树),是在数组的本身上进行的,没有用什么辅助空间 【评价】 堆排序在最坏情况下的时间复杂度也是O(nlog2n),这是相对快速排序的最大优点 堆排序的空间复杂度O(1),在所有...
  • 100数据导出到Excel的优化方案

    千次阅读 2019-12-23 18:48:04
     项目中需要从数据库中导出100数据,以excel形式下载并且只要一张sheet(打开这么大文件有多慢另说,呵呵)。  ps:xlsx最大容纳1048576行 ,csv最大容纳1048576行,xls最大容纳65536行,但是存放相同的数据...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,806
精华内容 8,722
关键字:

对一百万个数据进行快速排序