精华内容
下载资源
问答
  • 选择排序 归并排序 冒泡排序 堆排序 快速排序 等排序算法c++实现以及其效率比较 包括源代码
  • 编程分别实现快速排序算法、堆排序算法。 c语言的程序 数据结构
  • 包含了四种常见的排序算法,是招聘面试时常出的题目,最好自己编译跑一遍
  • 随机产生1000个0~9的数,并分别用堆排序快速排序,归并排序将产生的这1000个随机数排序,并将排序结果写入文件
  • 用C++语言实现的几个常见算法,里面有注解,方便大家理解,简单易学,都可以正常编译运行。
  • 插入排序2.希尔排序 1. 插入排序 步骤: 1.从第一个元素开始,该元素可以认为已经被排序 2.取下一个元素tem,从已排序的元素序列从后往前扫描 3.如果该元素大于tem,则将该元素移到下一位 4.重复步骤3,直到找到已...


    1. 插入排序

    步骤:

    1.从第一个元素开始,该元素可以认为已经被排序
    2.取下一个元素tem,从已排序的元素序列从后往前扫描
    3.如果该元素大于tem,则将该元素移到下一位
    4.重复步骤3,直到找到已排序元素中小于等于tem的元素
    5.tem插入到该元素的后面,如果已排序所有元素都大于tem,则将tem插入到下标为0的位置
    6.重复步骤2~5

    动图演示如下:在这里插入图片描述
    思路:
      在待排序的元素中,假设前n-1个元素已有序,现将第n个元素插入到前面已经排好的序列中,使得前n个元素有序。按照此法对所有元素进行插入,直到整个序列有序。
      但我们并不能确定待排元素中究竟哪一部分是有序的,所以我们一开始只能认为第一个元素是有序的,依次将其后面的元素插入到这个有序序列中来,直到整个序列有序为止。
    在这里插入图片描述
    代码如下:

    void InsertSort(int* arr, int n)
    {
    	for (int i = 0; i < n - 1; ++i)
    	{
    		//记录有序序列最后一个元素的下标
    		int end = i;
    		//待插入的元素
    		int tem = arr[end + 1];
    		//单趟排
    		while (end >= 0)
    		{
    			//比插入的数大就向后移
    			if (tem < arr[end])
    			{
    				arr[end + 1] = arr[end];
    				end--;
    			}
    			//比插入的数小,跳出循环
    			else
    			{
    				break;
    			}
    		}
    		//tem放到比插入的数小的数的后面
    		arr[end  + 1] = tem;
    		//代码执行到此位置有两种情况:
    		//1.待插入元素找到应插入位置(break跳出循环到此)
    		//2.待插入元素比当前有序序列中的所有元素都小(while循环结束后到此)
    	}
    }
    

    时间复杂度:最坏情况下为O(N*N),此时待排序列为逆序,或者说接近逆序
          最好情况下为O(N),此时待排序列为升序,或者说接近升序。
    空间复杂度:O(1)

    2.希尔排序

    步骤:
    1.先选定一个小于N的整数gap作为第一增量,然后将所有距离为gap的元素分在同一组,并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量,重复上述操作…
    2.当增量的大小减到1时,就相当于整个序列被分到一组,进行一次直接插入排序,排序完成。
    动图如下:
    在这里插入图片描述
    思路:
    希尔排序,先将待排序列进行预排序,使待排序列接近有序,然后再对该序列进行一次插入排序,此时插入排序的时间复杂度为O(N),

    代码如下:

    //希尔排序
    void ShellSort(int* arr, int n)
    {
    	int gap = n;
    	while (gap>1)
    	{
    		//每次对gap折半操作
    		gap = gap / 2;
    		//单趟排序
    		for (int i = 0; i < n - gap; ++i)
    		{
    			int end = i;
    			int tem = arr[end + gap];
    			while (end >= 0)
    			{
    				if (tem < arr[end])
    				{
    					arr[end + gap] = arr[end];
    					end -= gap;
    				}
    				else
    				{
    					break;
    				}
    			}
    			arr[end + gap] = tem;
    		}
    	}
    }
    

    时间复杂度平均:O(N^1.3)
    空间复杂度:O(1)

    3.选择排序

    思路:
    每次从待排序列中选出一个最小值,然后放在序列的起始位置,直到全部待排数据排完即可。
    实际上,我们可以一趟选出两个值,一个最大值一个最小值,然后将其放在序列开头和末尾,这样可以使选择排序的效率快一倍。

    动图如下:
    在这里插入图片描述
    代码如下:

    //选择排序
    void swap(int* a, int* b)
    {
    	int tem = *a;
    	*a = *b;
    	*b = tem;
    }
    void SelectSort(int* arr, int n)
    {
    	//保存参与单趟排序的第一个数和最后一个数的下标
    	int begin = 0, end = n - 1;
    	while (begin < end)
    	{
    		//保存最大值的下标
    		int maxi = begin;
    		//保存最小值的下标
    		int mini = begin;
    		//找出最大值和最小值的下标
    		for (int i = begin; i <= end; ++i)
    		{
    			if (arr[i] < arr[mini])
    			{
    				mini = i;
    			}
    			if (arr[i] > arr[maxi])
    			{
    				maxi = i;
    			}
    		}
    		//最小值放在序列开头
    		swap(&arr[mini], &arr[begin]);
    		//防止最大的数在begin位置被换走
    		if (begin == maxi)
    		{
    			maxi = mini;
    		}
    		//最大值放在序列结尾
    		swap(&arr[maxi], &arr[end]);
    		++begin;
    		--end;
    	}
    }
    

    时间复杂度:最坏情况:O(N^2)
          最好情况:O(N^2)
    空间复杂度:O(1)

    4.冒泡排序

    思路:
    左边大于右边交换一趟排下来最大的在右边

    动图如下:
    在这里插入图片描述
    代码如下:

    //冒泡排序
    void BubbleSort(int* arr, int n)
    {
    	int end = n;
    	while (end)
    	{
    		int flag = 0;
    		for (int i = 1; i < end; ++i)
    		{
    			if (arr[i - 1] > arr[i])
    			{
    				int tem = arr[i];
    				arr[i] = arr[i - 1];
    				arr[i - 1] = tem;
    				flag = 1;
    			}
    		}
    		if (flag == 0)
    		{
    			break;
    		}
    		--end;
    	}
    }
    

    时间复杂度:最坏情况:O(N^2)
          最好情况:O(N)
    空间复杂度:O(1)

    5.堆排序

    堆排可看之间这篇博文----->[堆排]

    6.快速排序

    5.1 hoare版本(左右指针法)

    思路:
    1、选出一个key,一般是最左边或是最右边的。
    2、定义一个begin和一个end,begin从左向右走,end从右向左走。(需要注意的是:若选择最左边的数据作为key,则需要end先走;若选择最右边的数据作为key,则需要bengin先走)。
    3、在走的过程中,若end遇到小于key的数,则停下,begin开始走,直到begin遇到一个大于key的数时,将begin和right的内容交换,end再次开始走,如此进行下去,直到begin和end最终相遇,此时将相遇点的内容与key交换即可。(选取最左边的值作为key)
    4.此时key的左边都是小于key的数,key的右边都是大于key的数
    5.将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作,此时此部分已有序

    单趟动图如下:
    在这里插入图片描述
    代码如下:

    //快速排序   hoare版本(左右指针法)
    void QuickSort(int* arr, int begin, int end)
    {
    	//只有一个数或区间不存在
    	if (begin >= end)
    		return;
    	int left = begin;
    	int right = end;
    	//选左边为key
    	int keyi = begin;
    	while (begin < end)
    	{
    		//右边选小   等号防止和key值相等    防止顺序begin和end越界
    		while (arr[end] >= arr[keyi] && begin < end)
    		{
    			--end;
    		}
    		//左边选大
    		while (arr[begin] <= arr[keyi] && begin < end)
    		{
    			++begin;
    		}
    		//小的换到右边,大的换到左边
    		swap(&arr[begin], &arr[end]);
    	}
    	swap(&arr[keyi], &arr[end]);
    	keyi = end;
    	//[left,keyi-1]keyi[keyi+1,right]
    	QuickSort(arr, left, keyi - 1);
    	QuickSort(arr,keyi + 1,right);
    }
    

    时间复杂度:
    在这里插入图片描述
    快速排序的过程类似于二叉树其高度为logN,每层约有N个数,如下图所示:在这里插入图片描述

    5.2 挖坑法

    5.2.1 递归

    思路:
    挖坑法思路与hoare版本(左右指针法)思路类似
    1.选出一个数据(一般是最左边或是最右边的)存放在key变量中,在该数据位置形成一个坑
    2、还是定义一个L和一个R,L从左向右走,R从右向左走。(若在最左边挖坑,则需要R先走;若在最右边挖坑,则需要L先走)

    后面的思路与hoare版本(左右指针法)思路类似在此处就不说了

    单趟动图如下:
    在这里插入图片描述
    代码如下:

    //快速排序法  挖坑法
    void QuickSort1(int* arr, int begin, int end)
    {
    	if (begin >= end)
    		return;
    	int left = begin,right = end;
    	int key = arr[begin];
    	while (begin < end)
    	{
    		//找小
    		while (arr[end] >= key && begin < end)
    		{
    			--end;
    		}
    		//小的放到左边的坑里
    		arr[begin] = arr[end];
    		//找大
    		while (arr[begin] <= key && begin < end)
    		{
    			++begin;
    		}
    		//大的放到右边的坑里
    		arr[end] = arr[begin];
    	}
    	arr[begin] = key;
    	int keyi = begin;
    	//[left,keyi-1]keyi[keyi+1,right]
    	QuickSort1(arr, left, keyi - 1);
    	QuickSort1(arr, keyi + 1, right);
    }
    

    5.2.2 非递归

    //单趟排
    int PartSort(int* arr, int begin, int end)
    {
    	int key = arr[begin];
    	while (begin < end)
    	{
    		while (key <= arr[end] && begin < end)
    		{
    			--end;
    		}
    		arr[begin] = arr[end];
    		while (key >= arr[begin] && begin < end)
    		{
    			++begin;
    		}
    		arr[end] = arr[begin];
    	}
    	arr[begin] = key;
    	int meeti = begin;
    	return meeti;
    }
    
    void QuickSortNoR(int* arr, int begin, int end)
    {
    	stack<int> st;
    	//先入右边
    	st.push(end);
    	//再入左边
    	st.push(begin);
    	while (!st.empty())
    	{
    		//左区间
    		int left = st.top();
    		st.pop();
    		//右区间
    		int right = st.top();
    		st.pop();
    		//中间数
    		int mid = PartSort(arr, left, right);
    		//当左区间>=mid-1则证明左区间已经排好序了
    		if (left < mid - 1)
    		{
    			st.push(mid - 1);
    			st.push(left);
    		}
    		//当mid+1>=右区间则证明右区间已经排好序
    		if (right > mid + 1)
    		{
    			st.push(right);
    			st.push(mid + 1);
    		}
    	}
    }
    

    5.3 前后指针法

    思路:
    1、选出一个key,一般是最左边或是最右边的。
    2、起始时,prev指针指向序列开头,cur指针指向prev+1。
    3、若cur指向的内容小于key,则prev先向后移动一位,然后交换prev和cur指针指向的内容,然后cur指针++;若cur指向的内容大于key,则cur指针直接++。如此进行下去,直到cur到达end位置,此时将key和++prev指针指向的内容交换即可。

    经过一次单趟排序,最终也能使得key左边的数据全部都小于key,key右边的数据全部都大于key。

    然后也还是将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作

    //快速排序法  前后指针版本
    void QuickSort2(int* arr, int begin, int end)
    {
    	if (begin >= end)
    		return;
    	int cur = begin, prev = begin - 1;
    	int keyi = end;
    	while (cur != keyi)
    	{
    		if (arr[cur] < arr[keyi] && ++prev != cur)
    		{
    			swap(&arr[cur], &arr[prev]);
    		}
    		++cur;
    	}
    	swap(&arr[++prev],&arr[keyi]);
    	keyi = prev;
    	//[begin,keyi -1]keyi[keyi+1,end]
    	QuickSort2(arr, begin, keyi - 1);
    	QuickSort2(arr, keyi + 1, end);
    
    }
    
    展开全文
  • C# 插入排序 冒泡排序 选择排序 快速排序 堆排序 归并排序 基数排序 希尔排序
  • 快速排序 堆排序

    2014-10-16 22:12:58
    快速排序 堆排序 C/C++实现,欢迎交流
  • 堆和堆排序:为什么说堆排序没有快速排序

    千次阅读 多人点赞 2019-01-22 10:23:50
    ------ 本文是学习算法的笔记,《数据结构与算法之美》,极客时间的课程 ------ 我们今天讲另外一种特殊的树,“堆(Heap)”。...尽管这两种排序算法的时间复杂度都是O(nlogn),甚至堆排序快速排序的时间...

    ------ 本文是学习算法的笔记,《数据结构与算法之美》,极客时间的课程 ------

    我们今天讲另外一种特殊的树,“堆(Heap)”。堆这种数据结构的应用场景非常多,最经典的莫过于堆排序了。堆排序是一种原地的、时间复杂度为O(nlogn)的排序算法。

    前面我们学过快速排序,平均情况下,它的时间复杂度为O(logn)。尽管这两种排序算法的时间复杂度都是O(nlogn),甚至堆排序比快速排序的时间复杂度还要稳定,但是,是实际软件开发中,快速的排序的性能要比堆排序好,这是为什么呢?

    如何理解“堆”?

    前面我们提到,堆是一种特殊的树。我们现在来看看,什么样的树才是堆。

    • 堆是一个完全二叉树;
    • 堆中每个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。
      在这里插入图片描述

    其中第1个和第2个是大顶堆,第3 个是小顶堆,第4个不是堆。除此之外,从图中还可以看出来,对于同一组数据,我们可以构建多种不再形态的堆。

    如何实现一个堆?

    要实现一个堆,我们先要知道,堆都支持哪些操作以及如何存储一个堆

    完全二叉树适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针,单纯地通过数组下标,就可以找到一个节点的左右子节点和父节点。在这里插入图片描述

    从上图中可以看出,数组下标为 i 的节点的左子节点,就是下标为 i2的节点,右子节点就是下标为 i2+1 的节点,父节点不是下标为 i/2 的节点。

    知道了如何存储一个堆,那我们再来看看,堆上的操作有哪些?我罗列了几个非常核心的操作,分别是往堆中插入一个元素和删除堆顶元素。(如果没有特殊说明,我下面都是拿大顶堆来讲解)。

    1、往堆中插入一个元素

    往堆中插入一个元素后,我们需要满足堆的两个特性。

    如果我们把新插入的元素放到堆的最后,如下图,是不符合堆的特性的。还需要调整,让其重新满足堆的特性。这个过程就叫作堆化(heapify)。堆化分为两种,从下往上和从上往下。先说从下往上的堆化方法。在这里插入图片描述

    堆化非常简单,就是顺着节点所在的考核体系,向上或者躺下,对比,然后交换。

    如下面的分解图,我们可以让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系,我们就互换两个节点。一直重复这个过程,直到父子节点之间满足刚说的那种大小关系。代码实现如下:在这里插入图片描述

    	public class Heap{
    		private int[] a; //数组,从下标1开始存储数据
    		
    		private int n; // 堆可以存储的最大数据个数
    		
    		private int count; // 堆中已经存储的数据个数
    		
    		public Heap(int capacity) {
    			a = new int[capacity + 1];
    			n = capacity;
    			count = 0;
    		}
    		
    		public void insert(int data) {
    			if(count >= n) {
    				return; // 没有空间了
    			}
    			++count;
    			a[count] = data;
    			int i = count;
    			while(i/2 > 0 && a[i] > a[i/2]) {
    				int temp = a[i];
    				a[i] = a[i/2];
    				a[1/2] = temp;
    				i = i/2;
    			}
    		}
    	}
    

    2、删除堆顶元素

    从堆的定义的第二条中,任何节点的值都大于等于(或小于等于)子树节点的值,我们可以发现,堆顶元素存储的就是堆中数据的最大值或者最小值。

    假设我们构造的是大顶堆,堆顶元素就是最大的元素。当我们删除堆顶元素之后,就需要把第二大的元素放到堆顶,那第二大元素肯定会出现在左右节点中。然后我们再迭代地删除第二大节点,以此类推,直到叶子节点被删除。

    这里我也画了一个分解图。不过这种方法有点问题,就是最后出来的堆并不满足完全二叉树的特性在这里插入图片描述

    实际上,我们稍微改变一下思路,就可以解决这个问题。我们把最后一个节点放到堆顶,然后利用同样的父子节点对比方法。对于不满足父子节点大小关系的,互换两个节点,并且重复这个过程,直到父子节点之间满足大小关系为止。这就是从上往下的堆化方法。

    因为我们移除的是数组中的最后一个元素,而在堆化的过程中,都是交换操作,不会出现数组中“空洞”,所以这种方法堆化之后的结果,肯定满足完全二叉树的特性。
    在这里插入图片描述

    		public void removeMax() {
    			if (count == 0) {
    				return;
    			}
    			a[1] = a[count];
    			--count;
    			heapify(a, count, 1);
    		}
    
    		private void heapify(int[] a, int n, int i) { // 自上往下堆化
    			while (true) {
    				int maxPos = i;
    				if (i * 2 <= n && a[i] < a[i * 2]) {
    					maxPos = i * 2;
    				}
    				if (i * 2 + 1 <= n && a[maxPos] < a[i * 2 + 1]) {
    					maxPos = i * 2 + 1;
    				}
    				if(maxPos == i) {
    					break;
    				}
    				int tem = a[i];
    				a[i] = a[maxPos];
    				a[maxPos] = tem;
    				i = maxPos;
    			}
    		}
    

    堆化的过程虽顺着节点所在的路径比较交换的,所以堆化的时间复杂度跟树的高度成正比,也就是O(logn)。插入数据和删除堆顶元素的主要逻辑就是堆化,所以往堆中插入一个元素和删除堆元素的时间复杂度都是O(logn)。

    如何基于堆实现排序?

    前面我们讲过好几种排序算法,有时间复杂度是(O2)的冒泡、插入、选择排序,有时间复杂度是O(nlogn)的归并、快速、线性排序。

    借助于堆这种数据结构实现的排序算法,就叫做堆排序。这种排序算法的时间复杂度非常稳定,是O(nlogn),并且它还是原地排序算法,如此优秀,这是怎么做到的呢?

    可以把堆排序的过程大致分解成两大步骤,建堆排序

    1、建堆

    首先将数组原地建成一个堆。所谓“原地”就是,不借助另一个数组,就在原数组上操作。建堆的过程,有两种思路。

    第一种是借助我们前面讲的,在堆中插入一个元素的思路。尽管数组中包含 n 个数据,但是我们可以假设,起初堆中只包含一个数据,就是下标为1的数据。然后,我们调用前面的插入操作,将下标从2到 n 的数据依次插入到堆中。这样我们就将包含n 个数据数组组织成了堆。

    第二种实现思路,跟第一种截然相反。第一种思路的处理过程是从前往后处理数据,并且每个数据插入堆中时,都是从下往上的堆化。而第二种实现的思路,是从后往前处理数组,并且每个数据都是从上往下堆化。

    如下图,因为叶子往下堆化只能自己跟自己比较,所以我们直接从第一个非叶子节点开始,依次堆化就行了。在这里插入图片描述

    		public void buildHeap(int[]a, int n) {
    			for(int i = n/2; i >= 1; --i) {
    				heapify(a, n, i);
    			}
    		}
    

    上面的代码中,我们对下标从 n/2 开始到 1 的数据进行堆化,下标是 n/2+1 到 n 的节点是叶子节点,我们不需要堆化。实际上,对于完全二叉树来说,下标从n/2+1 到 n的节点都是叶子节点。

    建堆操作的时间复杂度是多少呢?

    每个节点堆化的时间复杂度是O(logn),那 n/2+1 个节点堆化的总时间复杂度是不是就是O(nlogn)呢?这个答案虽然也没错,但这个值不够精确。实际上,堆排序的建堆过程时间复杂度是O(n)。

    因为叶子节点是不需要堆化的,所以需要堆化的节点从倒数第二层开始。每个节点堆化的过程中,需要比较和交换的节点个数,跟这个节点的高度 k 成正比。看下图在这里插入图片描述

    我们将每个非叶子节点的高度求和,就是下面的公式:
    在这里插入图片描述
    在这里插入图片描述

    最后再把 2h= n 代入,可得建堆的时间复杂充就是O(n)。

    2、排序

    建堆结束之后,数组中的数据已经是执照大顶堆的特性来组织的。数组中的第一个元素就是堆顶,也就是最大的元素。我们把它跟最后一个元素交换,那最大的元素就放到了下标为 n 的位置。

    这个过程有点类似上面讲的“删除堆顶元素”的操作,当堆顶元素移除之后,我们把下标为 n 的元素放到堆顶,然后再通过堆化的方法,将剩下的 n-1 个元素重新构建成堆。堆化完成之后,我们再取堆顶元素,放到下标是 n-1 的位置,一直重复这个过程,直到最后堆中只剩下为1个元素,排序工作就完成了。在这里插入图片描述

    		public void sort(int[]a, int n) {
    			buildHeap(a, n);
    			int k = n;
    			while( k > 1) {
    				int temp = a[k];
    				a[k] = a[1];
    				a[1] = temp;
    				--k;
    				heapify(a, k, 1);
    			}
    		}
    

    整个堆排序的过程,都只需要极个别的临时存储空间,所以堆排序是原地排序算法。堆排序包括建堆和排序两个操作,建堆过程的时间复杂度是O(n),排序过程的时间复杂度是O(nlogn),所以,堆排序整体的时间复杂度是O(nlogn)。

    堆排序是不稳定的排序算法,因为排序的过程,存在的最后一个节点跟堆项节点互换的操作,所以就有可能改变值相等数据的原始相对顺序。

    解答开篇

    现在,我们来看下,实际开发中,为什么快速排序要比堆排序性能好?

    第一、堆排序访问数据的方式没有快速排序友好。

    对于快速排序来说,数据是顺序访问的。而对于堆排序来说,数据是跳着访问的。比如,堆排序中,最重要的一个操作就是数据的堆化。比如下面这个例子,对堆顶进行堆化,会依次访问数组下标是1,2,4,8的元素,而不像快速排序那样,局部顺序访问,所以,这样对CPU缓存是不友好的。
    在这里插入图片描述

    第二、对于同样的数据,在排序过程中,堆排序算法的数据交换次数要多于快速排序。

    我们在讲排序的时候,提过两个概念,有序度和逆序度。对于基于比较的排序算法来说,整个排序过程是由两个基本操作组成的,比较和交换。快速排序交换的次数不会比逆序度多。

    但是堆排序的第一步是建堆,建堆的过程会打乱数据原有的相对选择顺序,导致数据有序度降低。比如对于一组已经有序的数据来说,经过建堆之后,数据反而变得更无序了。在这里插入图片描述

    展开全文
  • 四、堆排序 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度 五、冒泡排序 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度 六、快速排序 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度 七..
     
     
    

    八大排序算法

    一、直接插入

    1.基本思路

    在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

    2.代码实现

    • 1.遍历数组,每次循环从第二个数字往前插入
    • 2.设定插入数和得到已经排好序列的最后一个数的位数。temp和j=i-1。
    • 3.从最后一个数开始向前循环,如果插入数小于当前数,就将当前数向后移动一位。
    public static void insertSort(int[] data) {
        int temp;
        for(int i = 1;i < data.length; i++){// 取第i个数,插入前边的有序的序列
            temp = data[i];
            int j;
            for(j = i - 1; j>=0; j--) {// 从第i-1的位置上开始比较
                if(data[j] > temp) {// 若前面的数大,则往后挪一位
                    data[j+1] = data[j];
                } else {
                    break;// 否则,说明要插入的数比较大
                }
            }
            data[j+1] = temp;// 找到这个位置,插入数据
        }
    }
    

    3.时间复杂度和空间复杂度

    直接插入排序的平均复杂度为O(n²),最坏时间复杂度:O(n²),空间复杂度:O(1),没有分配内存。

    二、希尔排序

    针对直接插入排序下的效率问题,有人对此进行了改进与升级,这就是现在的希尔排序。希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

    1.基本思路

    • 1.数的个数为length,i=length/2,将下标差值为i的数分为一组,构成有序序列。

    • 2.再取i=i/2 ,将下标差值为i的数分为一组,构成有序序列。

    • 3.重复第二步,直到k=1执行简单插入排序。

    思路:

    • 1.希尔排序(shell sort)这个排序方法又称为缩小增量排序,是1959年D·L·Shell提出来的。该方法的基本思想是:设待排序元素序列有n个元素,首先取一个整数increment(小于n)作为间隔将全部元素分为increment个子序列,所有距离为increment的元素放在同一个子序列中,在每一个子序列中分别实行直接插入排序。然后缩小间隔increment,重复上述子序列划分和排序工作。直到最后取increment=1,将所有元素放在同一个子序列中排序为止。
    • 2.由于开始时,increment的取值较大,每个子序列中的元素较少,排序速度较快,到排序后期increment取值逐渐变小,子序列中元素个数逐渐增多,但由于前面工作的基础,大多数元素已经基本有序,所以排序速度仍然很快。

    希尔排序举例:
    在这里插入图片描述

    2.代码实现

    • 1.遍历数组,每次循环从第二个数字往前插入
    • 2.设定插入数和得到已经排好序列的最后一个数的位数。temp和j=i-1。
    • 3.从最后一个数开始向前循环,如果插入数小于当前数,就将当前数向后移动一位。

    (1)首先确定每一组序列的下标的间隔,循环每次需要的间隔:int i = length/2; i >0 ; i /= 2

    (2)然后将每一组序列中元素进行插入排序,第二组第一个插入的数字是第一组第一个插入数字之后的那个数组,从i之后每个数字都要进行插入排序,就是插入的序列是各自不同的序列,不是一个一个子序列循环,而是在一个循环中for (int j=i;j<length;j++)完成所有子序列的插入排序。

    (3)直到i=0为止。

    public static void shellSort(int[] array) {
        int length = array.length;
        for (int i = length / 2; i > 0; i /= 2) {//序列的间隔,一直到间隔为一,这时候就只有一个子序列
            for (int j = i; j < length; j++) {//从i之后每个数字都要进行插入排序,就是插入的序列是各自不同的序列
                int temp = array[j];//里面就是直接插入算法
                int k;
                for (k = j - i; k >= 0; k -= i) {//实现各个数字插入排序到不同的序列中,直到间隔为1的时候,只有一个序列,就是完全的一个直接插入排序
                    if (temp < array[k]) {
                        array[k + i] = array[k];
                    } else {
                        break;
                    }
                }
                array[k + i] = temp;//把数字插入到位置上
            }
        }
        System.out.println(Arrays.toString(array));
    }
    

    3.时间复杂度和空间复杂度

    希尔排序的平均时间复杂度为O(n²),空间复杂度O(1) 。

    三、简单选择

    1.基本思路

    基本原理如下:对于给定的一组记录,经过第一轮比较后得到最小的记录,然后将该记录的位置与第一个记录的位置交换;接着对不包括第一个记录以外的其他记录进行第二次比较,得到最小记录并与第二个位置记录交换;重复该过程,直到进行比较的记录只剩下一个为止。

    2.代码实现

    • 1.确定要插入最小值的位置,从0开始到最后int i = 0; i <len ; i++
    • 2.将每次开始位置上的数字暂定为最小值min,从开始数字之后一个个和min比较,再把最小值存放到min
    • 3.将最小值所在位置上的数字和开始位置上的数字交换
    public static void selectSort(int[] array) {
        int len = array.length;
        for (int i = 0; i < len; i++) {//确定每次开始的位置
            int min = array[i];//设定开始数字为最小的值最小值
            int flag = i;
            for (int j = i + 1; j < len; j++) {//把最小值存放到min,从开始数字向后一个个和min比较,再把最小值存放到min
                if (min > array[j]) {
                    min = array[j];
                    flag = j;
                }
            }
            if (flag != i) {
                array[flag] = array[i];
                array[i] = min;
            }
        }
        System.out.println(Arrays.toString(array));
    }
    

    3.时间复杂度和空间复杂度

    简单选择排序的时间复杂度为O(n²)

    四、堆排序

    1.基本思路

    • 1.若array[0,…,n-1]表示一颗完全二叉树的顺序存储模式,则双亲节点指针和孩子结点指针之间的内在关系如下:
    任意一节点指针 i:
    父节点:i==0 ? null : (i-1)/2
    左孩子:2*i + 1
    右孩子:2*i + 2
    
    • 2.堆得定义
    n个关键字序列array[0,...,n-1],当且仅当满足下列要求:(0 <= i <= (n-1)/2)
    ① array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]; 称为小根堆;
    ② array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]; 称为大根堆;
    
    • 3.建立大顶堆

    n个节点的完全二叉树array[0,…,n-1],最后一个节点n-1是第(n-1-1)/2个节点的孩子。对第(n-1-1)/2个节点为根的子树调整,使该子树称为堆。

    对于大根堆,调整方法为:若【根节点的关键字】小于【左右子女中关键字较大者】,则交换。

    之后向前依次对各节点((n-2)/2 - 1)~ 0为根的子树进行调整,看该节点值是否大于其左右子节点的值,若不是,将左右子节点中较大值与之交换,交换后可能会破坏下一级堆,于是继续采用上述方法构建下一级的堆,直到以该节点为根的子树构成堆为止。

    反复利用上述调整堆的方法建堆,直到根节点。

    • 4.堆排序(大顶堆)
    ①将存放在array[0,...,n-1]中的n个元素建成初始堆;
    ②将堆顶元素与堆底元素进行交换,则序列的最大值即已放到正确的位置;
    ③将数组中array[0,...,n-1]前n-1个元素再次形成大根堆,再重复第②③步,直到堆中仅剩下一个元素为止。
    

    2.代码实现

    
    /**
        *  大顶堆排序
        * @param array
        */
    public static void maxHeapSort(int[] array) {
        int i;
        int len = array.length;
        // 构建大顶堆
        for (i = len / 2 - 1; i >= 0; i--) {
            adjustMaxHeap(array, i, len);
        }
        // 堆顶是最大值,交换堆顶和最后一个数,再重新调整最大堆,下一次循环   i--
        for (i = len - 1; i >= 0; i--) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            adjustMaxHeap(array, 0, i);
        }
        System.out.println(Arrays.toString(array));
    }
    
    private static void adjustMaxHeap(int[] a, int pos, int len) {
        int temp;
        int child;
        for (temp = a[pos]; 2 * pos + 1 < len; pos = child) {
            // 数组从0开始,r(i)>=r(2i) r(i)>=r(2i+1)  对应 pos => 2 * pos + 1 和 2 * pos +2
            child = 2 * pos + 1;
            // 有右孩子,且右孩子数值更大
            if (child + 1 < len && a[child] < a[child + 1]) {
                child++;
            }
            // 最大的孩子大于根节点
            if (a[child] > temp) {
                a[pos] = a[child];
            } else {
                break;
            }
        }
        a[pos] = temp;
    }
    

    3.时间复杂度和空间复杂度

    时间复杂度:建堆:o(n),每次调整o(log n),故最好、最坏、平均情况下:o(n*logn);

    五、冒泡排序

    1.基本思路

    一次冒泡将序列中从头到尾所有元素两两比较,将最大的放在最后面。

    将剩余序列中所有元素再次两两比较,将最大的放在最后面。

    重复第二步,直到只剩下一个数。

    2.代码实现

    /**
     * @author fupeng
     * 冒泡排序优化第二版
     * 第一版优化增加flag标记,没有数字交换直接return,最优时间复杂度O(n)
     * 第二版优化,增加tempPostion记录内循环最后一次交换的位置,来缩减内循环的次数
     */
    public static void bubbleSort(int[] array) {
        int len = array.length - 1;
        // 开辟一个临时空间, 存放交换的中间值
        int temp;
        // 记录最后一次交换的位置
        int tempPostion = 0;
        // 要遍历的次数
        for (int i = 0; i < array.length - 1; i++) {
            int flag = 1; // 设置一个标志位
            // 依次比较相邻两个数的大小,遍历一次后,会将前面没有排好序的最大值放到后面位置
            for (int j = 0; j < len; j++) {
                // 比较相邻的元素,如果前面的数大于后面的数,交换
                if (array[j] > array[j + 1]) {
                    temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                    // 发生交换,标志位置0
                    flag = 0;
                    // 记录交换的位置
                    tempPostion = j;
                }
            }
            // 把最后一次交换的位置给len,来缩减内循环的次数
            len = tempPostion;
            // 如果没有交换过元素,则已经有序
            if (flag == 1) {
                System.out.println(Arrays.toString(array));
                return;
            }
        }
        System.out.println(Arrays.toString(array));
    }
    

    3.时间复杂度和空间复杂度

    冒泡排序的最好时间复杂度为O(n),最坏时间复杂度为O(n²),平均时间复杂度为O(n²),空间复杂度为O(1),它是一种稳定的排序算法。

    六、快速排序

    1.基本思路

    快速排序使用分治策略来把一个序列(list)分为两个子序列(sub-lists)。步骤为:

    • 1.从数列中挑出一个元素,称为"基准"(pivot)。
    • 2.重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
    • 3.递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。

    递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

    2.代码实现

    public static void quickSort(int[] array) {
        sort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }
    
    private static void sort(int[] a, int low, int high) {
        int i = low;
        int j = high;
        if (a.length <= 1) {
            return;
        }
        if (i >= j) {
            return;
        }
        int index = a[i];
        while (i < j) {
            while (i < j && a[j] >= index)
                j--;
            if (a[j] < index)
                a[i++] = a[j];
            while (i < j && a[i] <= index)
                i++;
            if (a[i] > index)
                a[j--] = a[i];
        }
        a[i] = index;
        sort(a, low, i - 1);
        sort(a, i + 1, high);
    }
    

    3.时间复杂度和空间复杂度

    虽然 快排的时间复杂度达到了 O(n²),但是在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好。

    七、归并排序

    1.基本思路

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

    • 1.分而治之
      在这里插入图片描述

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

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

    在这里插入图片描述
    在这里插入图片描述

    2.代码实现

    public static void mergeSort(int[] array) {
        int[] temp = new int[array.length];// 在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
        mergeSort(array, 0, array.length-1, temp);
        System.out.println(Arrays.toString(array));
    }
    
    private static void mergeSort(int[] arr, int left, int right, int []temp) {
        if(left < right) {
            int mid = (left+right) / 2;
            mergeSort(arr, left, mid, temp);// 左边归并排序,使得左子序列有序
            mergeSort(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++];
        }
    }
    

    3.时间复杂度和空间复杂度

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

    八、基数排序

    1.基本思路

    • 1.基数排序的思想就是先排好各位,然后排好各位的基础上排十位,以此类推,直到遍历最高位 次,排序结束(仔细理解最后一句话)
    • 2.基数排序不是比较排序,而是通过分配和收集的过程来实现排序
    • 3.初始化10个桶(固定的),桶下标为0-9
    • 4.通过得到待排序数字的个十百等位的数字,把这个数字对应的item放到对应的桶中
    • 5.基数排序有两种排序方式:LSD和MSD,最小位优先(从右边开始)和最大位优先(从左边开始)

    在这里插入图片描述

    2.代码实现

    public static void radixSort(int[] array) {
        ArrayList<ArrayList<Integer>> queue = new ArrayList<>();
        for (int i = 0; i <10 ; i++) {
            queue.add(new ArrayList<>());// 创建一个基数从0---9 每个数字上都是一个list
        }
        // 找到最大值,并判断最大值是几位数
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
        }
        int time = 0;
        while (max > 0) {
            max /= 10;
            time++;
        }
        for (int i = 0; i < time; i++) {// 循环每一个位数(个位、十位、百位)
            for (int j = 0; j < array.length; j++) {// 循环数组,取每一个值
                int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
                ArrayList<Integer> queue3 = queue.get(x);
    
                queue3.add(array[j]);
                queue.set(x, queue3);
            }
            int count = 0;
            for (int k = 0; k < 10; k++) {
                while (queue.get(k).size() > 0) {
                    ArrayList<Integer> queue4 = queue.get(k);
                    array[count] = queue4.get(0);
                    queue4.remove(0);
                    count++;
                }
            }
        }
    }
    

    3.时间复杂度和空间复杂度

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

    总结

    在这里插入图片描述

    引用:

    https://www.cnblogs.com/mensan/p/10570050.html

    https://www.cnblogs.com/jyroy/p/11248691.html

    https://www.cnblogs.com/chengxiao/p/6194356.html

    https://www.jianshu.com/p/8340dfaea3af

    展开全文
  • 插入排序 冒泡排序 堆排序 基数排序 选择排序 快速排序的源码 java实现
  • 28|堆和堆排序为什么说堆排序没有快速排序快 28|堆和堆排序为什么说堆排序没有快速排序快 $Heap$ $O(n\log 我们今天讲另外一种特殊的树 堆 堆这种数据结构的应用场景非常多最经典的莫过于堆排序堆排序是一种原地的...
  • 希尔排序,堆排序快速排序

    1.希尔排序

    插入排序的改进算法,不稳定的排序算法,空间复杂度为O(1)

        public static void shellSort(int a[]){
            int k=a.length;
            int temp;
            while (k>1) {
                k=(k+1)/2;
                for (int i = 0; i < a.length-k; i++) {
                    if (a[i]>a[i+k]) {
                        temp=a[i];
                        a[i]=a[i+k];
                        a[i+k]=temp;
                    }
                }
            }
        }

    2.快速排序

    冒泡排序的改进算法,不稳定的排序算法
    空间复杂度在O(log2n)和O(n)之间
    时间复杂度在O(n)和O(n2)之间,平均时间复杂度为O(nlog2n),而当数组初始有序的条件下,快速排序会退化为冒泡排序

    //一趟快速排序算法
    public static int partition(int i,int j){
            int temp=a[i];
            while (j>i) {
                while (temp<=a[j]&&j>i) {
                    j--;
                }
                if (j>i) {
                    a[i]=a[j];
                    i++;
                }
                while (temp>=a[i]&&j>i) {
                //写temp>=a[i],将i误写成了j浪费了大量时间排错
                    i++;
                }
                if (j>i) {
                    a[j]=a[i];
                    j--;
                }
            }
            a[i]=temp;
            return i;
        }
        //static int count=0;
        //递归调用partition()函数,进行多趟排序直至整个数组有序
        public static void  qSort(int low,int high){
            if (high>low) {
                int i=partition(low, high);
                qSort(low, i-1);
                qSort(i+1, high);
                //System.out.print(++count);
            }
        }
        public static void quickSort(int []a){
            qSort(0, a.length-1);
        }

    3.堆排序

    树形排序的改进型排序算法,不稳定的排序算法
    空间复杂度O(1)
    时间复杂度O(nlog2n)

        public static void shift(int low,int high){
            int i=low;
            int j=2*i+1;
            int temp=a[i];
            while (j<high) {
                if (j<high-1&&a[j]>a[j+1]) {
                    j++;
                }
                if (a[i]>a[j]) {
                    a[i]=a[j];
                    i=j;
                    j=2*i+1;
                }else {
                    j=high+1;
                }
            }
            a[i]=temp;
        }
        public static void heapSort(){
            int len=a.length;
            int temp;
            //初始化堆
            for (int i=len/2-1;i>=0;i--) {
                shift(i, len);
            }
            //将最小关键字值交换到后面,再调整堆
            for (int i=len-1;i>0;i--) {
                temp=a[0];
                a[0]=a[i];
                a[i]=temp;
                shift(0, i);
            }
        }
    展开全文
  • 直接插入排序 选择排序 堆排序 归并排序 快速排序 冒泡排序等七种排序方法
  • C 排序 数据结构 链表 堆排序 希尔排序 快速排序 递归排序。详细解释了每个排序方法原理,并带有程序代码。是学习C语言的绝好资料
  • 第一、堆排序访问数据的方式没有快速排序友好。 对于快速排序来说,数据是顺序访问的。而对于堆排序来说,数据是跳着访问的。比如,堆排序中,最重要的一个操作就是数据的堆化。比如下面这个例子,对堆顶进行堆化,...
  • 算法导论 快速排序 堆排序 算法导论上的算法实现更加精简高效 代码可编译运行测试 加了测试用例 加了注释
  • 本人用我的方法实现了快速排序堆排序,并对比了下性能,发现,快速排序性能比堆排序高很多。注:我的结果可能是由于我的算法设计和代码设计导致的,不要因此造成误导。
  • 用顺序表实现堆排序快速排序,输入的元素个数不限可以直接确定,C语言
  • 简单实现了快速排序堆排序堆排序采用和数据结构上面不同的向上筛选法,可以编译,运行,可供学习
  • 直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
  • 归并排序 快速排序 堆排序 java实现
  • 堆排序、归并排序、快速排序总结

    千次阅读 2017-03-12 10:27:38
    昨天刚把这三个排序算法复习了一遍,其中归并排序和快速排序特别的重要,一定要熟练并理解透彻! 以下排序的结果都默认为非递减   1、堆排序(默认大顶堆) 堆排序的思想:首先构建一个完全二叉树,从最大的非...
  • 用java语言实现冒泡排序、插入排序、堆排序快速排序、归并排序、希尔排序、桶排序,并且对各种排序算法进行性能的比较。
  • c++实现堆排序快速排序堆排序比较,未分割头文件,可自行分割,加入counter,记录总运算时间
  • 冒泡排序,选择排序,插入排序,希尔排序,堆排序,归并排序,快速排序源码实现,里面有详细讲解,对新手应该有帮助
  • 快速排序、归并排序、堆排序 并比较排序时间 数据结构与算法
  • 数据结构:快速排序堆排序、归并排序、希尔排序 c++实现
  • 堆排序快速排序比较

    千次阅读 2018-12-26 19:59:09
      时间复杂度  ... 快速排序 O(nlogn) O(nlogn) O(n*n)平方 O(1)原地 否(涉及到左右数据交换) 堆排序 O(nlogn) O(nlogn) O(nlogn) O(1)原地 否(涉及...
  • 排序算法 选择排序: 插入排序: 合并排序: 快速排序堆排序

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 128,580
精华内容 51,432
关键字:

堆排序快速排序