`

几种排序算法复习

阅读更多

       对排序算法的复习——插入排序、希尔排序、堆排序、归并排序、快速排序、桶式排序、外部排序。

 

一、最简单的插入排序

 

       插入排序由N-1趟排序组成,对于p=1到N-1趟,插入排序保证从0到位置p上的元素为已排序状态。什么意思呢,比如说我们要对如下一组整数进行插入排序(排序后要从小到大):

34, 8, 64, 51, 32, 21

       当排序第一趟的时候,我们比较前两个数,也就是34和8,我们发现,34大于8,那么第一趟排序后的结果就是:

8, 34, 64, 51, 32, 21

        当排序第二趟的时候,我们比较前三个数,也就是8,34和64,我们将64与34比较,发现64大于34,那么这趟排序就结束了(因为经过第一趟排序,我们知道34一定比前一个数大,也就是排序算法的定义规则),那么第二趟排序后的结果就是:

8, 34, 64, 51, 32, 21

        当排序第三趟的时候,我们比较四个数,也就是将第四个数51,与第三位数比较,我们发现51小于64,既然小于,那么再让51与34比较,发现51大于34,那么到此,第三趟排序结束了,所以第三趟排序后的结果就是:

8, 34, 51, 64, 32, 21

        以此类推,一直进行到第5趟(这些数的长度减一)为止,排序算法就结束了,数也就排序完了。这就是排序算法。

        插入排序算法的性能不高,算是比较耗时的了,我们可以想想,因为不管怎么样都要进行N-1趟排序,那么肯定耗时了。我的git库里面有代码:https://github.com/hejiawang/Arithmetic.git    感兴趣的道友可以帮我指正一下。

对于给出的示例的完整的排序过程如图:



 核心代码:

public static void insertionSort(int[] array) {
	int j;
	for (int i = 1; i < array.length; i++) {
		int temp = array[i];
		for (j = i; j > 0 && temp < array[j - 1]; j--) {
			array[j] = array[j - 1];
		}
		array[j] = temp;
	}
}

 
二、希尔排序

       希尔排序要使用一个增量序列(稍后就会明白),在使用增量h的一趟排序之后,对于每一个位置i 我们都有a[i] <= a[i+h],所以相隔h的元素都被排序了。

       挺不好理解的,举个例子,比如我们要对如下的13个数从小到大进行希尔排序,

81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15

        首先我们使用增量序列5进行排序,什么意思呢?就是在上面的这个数列中找第五个数,也就是12,让12这个数的左右两边的数进行比较,比如我们将81和35进行比较,81大于35,那么我们就将这两个数调换位置,然后94和17比较,11和95比较,96和28比较,凡是坐边大于右边的,我们都将这两个数调换位置,经过这样排序之后,我们能够保证,以12为中心的左右两边的数,第一个小于小于第5+1个数,第2个数小于5+2个数,以此类推;这次排序之后,从第五位也就是数字12开始数,在数5个数,也就是28,让12与58比较,35与41比较。。。。重复上一个步骤;然后从28开始在数5个数也就是15,发现15后面没数了。那么第一次的希尔排序就算结束了。

       读起来感觉希尔排序挺麻烦的,但是,希尔排序确实挺麻烦的。。。^_^    但是如果选对了增量序列希尔排序的效率还是和可观的。难就难在怎么选择增量序列。

上面的例子经过希尔排序的各个步骤如下:


 核心代码:

public static void shellSort(int[] array) {
	int j;
	for (int gap = array.length / 2; gap > 0; gap /= 2) {
		for (int i = gap; i < array.length; i++) {
			int tmp = array[i];
			for (j = i; j >= gap && tmp < array[j - gap]; j -= gap) {
				array[j] = array[j - gap];
			}
			array[j] = tmp;
		}
	}
}

 

 三、堆排序

       堆排序到现在还不太明白。。。不做记录了。以后机缘巧合弄明白了,在记下来。。。。

 

四、归并排序

       归并排序就是将一个数组分成两份(也可以多分弄成多路归并排序),将两个数组的第一个数进行比较,把较小的那个数移到一个新的空数组中,然后重复这个操作,最后得到的新数组,就是一个经过排序的数组了。这就是归并排序,在外部排序中用归并排序的思想比较多,下面给出一个示例图:



 

五、快速排序

       快速排序对Java货c++的基本类型的排序特别有用,快速排序就是在一个数组中选取一个数作为枢纽元,在这些数中,凡是比这个数小的,放在一边,比这个数大的放一边,然后在这两边中在按这种方式排序下去,知道排序完成。效率很好。

 

六、桶式排序

       要使用桶式排序,就要知道数组中最大的数是多少,然后构建一个比这个数大一的一个空数组Array,把这个数组的各个项初始化为0,于是,当读到一个数a时,就在数组的Array[a]位置上增一,在所有的输入数据读入后,扫描数组Array,打印出排序后的表,就是经过排序的数了。。很有意思的一种排序:



 七、外部排序

       所谓外部排序就是没有内存的概念了,但是可以用磁带啊什么的,其他的思想就和归并排序一样了,还有多路归并排序,就是把原来的数组分割成对份,思想就是这样了,不重复了。。。

 


 

  • 大小: 22.2 KB
  • 大小: 25.2 KB
  • 大小: 29.5 KB
  • 大小: 17.3 KB
1
0
分享到:
评论

相关推荐

    排序算法复习大全(Java实现).doc

    本文将深入探讨几种经典的排序算法,并通过Java实现来加深理解。 首先介绍的是插入排序。插入排序的工作原理是将未排序的元素逐个插入到已排序的序列中,确保每次插入后序列都是有序的。在Java代码中,我们定义了一...

    Java基础复习笔记11基本排序算法

    本文档主要介绍了Java中的几种基本排序算法,包括冒泡排序、快速排序、选择排序、堆排序等,并通过具体的代码实例对每种排序算法进行了详细的解释。文档旨在帮助初学者理解不同排序算法的工作原理及其在实际开发中的...

    算法分析期末复习

    - **定义**:插入排序是一种简单的排序算法,其工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 - **核心思想**:插入排序的核心在于将一个记录插入到已经排好序...

    算法-数据结构之【排序】复习题.rar

    - 算法描述:要求详细解释每种排序算法的工作原理。 - 时间复杂度分析:计算各种排序算法的最好、最坏和平均时间复杂度。 - 空间复杂度分析:讨论排序算法的空间需求,特别是是否是原地排序。 - 案例分析:给出特定...

    西电算法课程期末复习资料.zip

    课程内容如下: 八大排序的详细讲解,求解递归式的复杂度,常用的几种算法和典例,贪心有活动选择,部分背包,迪杰斯特拉等,动规的有装配线调度,最大子段和,0-1背包,最长公共子序列(LCS),最长回文子序列的...

    浙教算法与程序设计VB排序复习PPT课件.pptx

    2. 熟练编写和运行这两种排序算法的VB代码。 3. 分析不同类型的排序题目,培养解决问题的能力。 此外,课件还提到了对比较次数和交换次数的研究,以及冒泡排序和选择排序在执行时间和效率上的比较,这对于优化算法...

    Python常见排序算法汇总共2页.pdf.zip

    7. 计数排序(Counting Sort)、桶排序(Bucket Sort)和基数排序(Radix Sort):这三种排序算法属于非比较型排序,它们不依赖于元素之间的比较,而是基于特定的特性(如元素的范围、分布或基数)。这些方法通常...

    NOIP初赛复习13排序与算法复杂度.pdf

    主要包括以下几种: - **冒泡排序** - **基本思想**:通过不断比较相邻元素并根据需要交换它们的位置来实现排序。 - **排序方法**:遍历整个数组,每次比较相邻的两个元素,如果前一个元素大于后一个元素,则交换...

    中科大算法设计与分析复习重点.zip

    2. **排序与搜索算法**:包括冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等经典排序算法的原理、实现和复杂度分析。搜索算法如二分查找、哈希查找也是重点。 3. **分治策略**:如归并排序、快速排序...

    寻找第k小元素 基本算法复习

    在此,我们将深入探讨几种寻找第k小元素的算法,并分析它们的时间复杂度和适用场景。 1. 快速选择算法: 快速选择是快速排序的一个变体,由C.A.R. Hoare提出。它的基本思想是通过分治策略来找到数组中的第k小元素。...

    计算机算法设计与分析期末考试复习资料汇总

    3. **排序与查找算法**:如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等排序算法的原理、优缺点及复杂度分析;二分查找、哈希查找、B树和B+树等查找算法的理解和应用。 4. **图论算法**:深度优先...

    计算机算法复习重点资料PPT学习教案.pptx

    3. **归并排序**:归并排序是一种稳定的排序算法,它利用了分治的思想。将数组分为两半,分别排序,然后合并两个已排序的子数组,形成最终的有序数组。在PPT中展示了归并排序的过程和一个具体的例子。 4. **图的...

    数据结构与算法总复习(知识点+习题+关键代码)

    首先,我们来看看几种基本的数据结构: 1. **栈**:栈是一种后进先出(LIFO)的数据结构,常用于表达式求值、递归调用等场景。在顺序栈中,判断栈是否为空的条件是栈底指针`s-&gt;top`等于-1,判断栈满的条件是`s-&gt;top...

    数据结构与算法复习题.docx

    - **查找和排序算法**:例如顺序查找、折半查找、二分查找、插入排序、选择排序、快速排序和归并排序。 6. **字符串**: - **空串**:没有字符的串,长度为零。 7. **数组和内存布局**: - **二维数组**:存储...

    数据结构重要算法(含排序、查找)期末复习用

    **排序算法**是用于重新排列一组数据,使得数据按照特定顺序排列。排序的效率直接影响到程序的性能。常见的排序算法包括: 1. **快速排序**:由一次分划过程构成,通过选择一个基准元素并将数组分为小于和大于基准...

    天津工业大学《算法设计与分析》期末复习题(含答案).pdf

    - 算法在实际软件开发中的应用,例如排序算法在数据库管理系统中的应用。 - 大数据处理中的算法优化,如MapReduce框架中的算法设计。 由于给定的文件内容重复且无实际算法内容,以上知识点是根据“算法设计与分析”...

    C语言算法考试复习题

    1. **字符数组排序**:题目的代码实现了一个简单的冒泡排序算法,用于对字符数组中下标为偶数的元素进行升序排序。它通过两层循环遍历数组,比较并交换相邻的偶数下标元素,确保排序正确。注意,字符串在C语言中被视...

    算法导论 黑皮书 期末复习笔记

    1. **排序与搜索**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等基本排序算法,以及线性搜索、二分搜索、哈希表搜索等搜索方法。这些算法在实际编程中非常常见,理解它们的时间复杂度和空间...

    【精品课件】数据结构与算法 数据结构与C语言 data structure课程 第8章 排序(共223页).ppt

    课程中提到了几种常见的排序算法: 1. 插入排序:分为直接插入排序和折半插入排序。直接插入排序通过不断将新元素插入已排序的子序列中,逐步构建完整的有序序列;折半插入排序利用折半查找来确定插入位置,减少了...

Global site tag (gtag.js) - Google Analytics