一、冒泡排序
1.1 概念
重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
1.2 运作
1、比较相邻的元素。如果第一个比第二个大,就交换他们两个。
2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤,除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
平均时间复杂度 最差空间复杂度 最佳算法
О(n²) О(n²) NO
1.3 代码
/**
* 冒泡排序
* 搜索整个值列,比较相邻元素,如果两者的相对次序不对,则交换它们
* @param numbers 待排序数据
* @return
*/
private void maoPao(int[] numbers) {
for(int i = numbers.length-1;i>=0;i--){//循环所有未排序数据
for(int j=0;j<i;j++){//两两比较
if(numbers[j]>numbers[j+1]){
int temp = numbers[j];
numbers[j]=numbers[j+1];
numbers[j+1]=temp;
}
}
}
}
二、选择排序
2.1 概念
首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾(目前已被排序的序列)。以此类推,直到所有元素均排序完毕。
2.2 运作
1、所有序列中找到最大的放第一位
2、除去第一位,剩余所有序列中找到最大的放第二位
3、以此类推直至排序完成
平均时间复杂度 最差空间复杂度 最佳算法
О(n²) О(n) total, O(1)auxiliary 偶尔出现
2.3 代码
/**
* 选择排序:
* 搜索整个值列,以找到最小值。将该值与值列中第一个位置上的值进行交换。
* 搜索剩下的值列(第一个除外),以找到其中的最小值,然后将其与值列中第二个位置上的值进行交换。
* @param numbers 待排序数据
* @return
*/
private void xuanZe(int[] numbers) {
for(int i = 0 ; i <numbers.length ;i++){
int max = i;
for(int j = i+1 ; j <numbers.length-1 ;j++){
if(numbers[j]<numbers[max]){
max = j;
}
}
if(max != i){
int temp = numbers[i];
numbers[i]=numbers[max];
numbers[max]=temp;
}
}
}
三、插入排序
3.1 概念
工作原理是通过构建有序序列,
对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排
序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
3.2 运作
1、从第一个元素开始,该元素
可以认为已经被排序2、取出下一个元素,在已经排序的元素序列中从后向前扫描3、如果该元素(已排序)大于新元素,将该元素移到下一位置4、重复步骤3,
直到找到已排序的元素小于或者等于新元素的位置5、将新元素插入到该位置后6、重复步骤2~5
平均时间复杂度 最差空间复杂度 最佳算法
О(n²) 总共O(n) ,需要辅助空间O(1) No
3.3 代码
/**
* 插入排序:
* 前两个排序,然后降低三个与前两个排序;在将第四个与前三个排序,依次直至排序结束
* @param numbers 待排序数据
* @return
*/
private void chaRu(int[] numbers) {
for(int i = 1 ; i <numbers.length ;i++){
int one = numbers[i];
for(int j = i-1;j>=0;j--){
if(numbers[j]>one){
numbers[j+1]=numbers[j];
numbers[j]=one;
}
}
}
}
四、快速排序
4.1 概念
快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。
步骤为:
1)设置两个变量I、J,排序开始的时候:I=1,J=N;
2)以第一个数组元素作为关键数据,赋值给X,即 X=A[1];
3)从J开始向前搜索,即由后开始向前搜索(J=J-1),找到第一个小于X的值,让该值与X交换;
4)从I开始向后搜索,即由前开始向后搜索(I=I+1),找到第一个大于X的值,让该值与X交换;
5)重复第3、4步,直到 I=J;
递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
4.2 运作
平均时间复杂度 最差空间复杂度 最佳算法
Ο(n log n) 根据实现的方式不同而不同 有时是
学习参考:
http://tscjsj.blog.51cto.com/412451/84587
http://tscjsj.blog.51cto.com/412451/84590
未完待续
分享到:
相关推荐
Python算法之---冒泡,选择,插入排序算法.py
本文将深入探讨四种在C++中实现的常见排序算法:插入排序、冒泡排序、堆排序和快速排序。这些算法各有特点,适用于不同的场景,理解并掌握它们对于提升编程能力至关重要。 1. **插入排序**: 插入排序是一种简单的...
本篇文章将详细讨论几种常见的排序算法:选择排序、冒泡排序、插入排序、合并排序以及快速排序,分析它们的算法原理、时间效率,并通过经验分析验证理论分析的准确性。 **1. 选择排序(Selection Sort)** 选择排序...
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
本主题将详细探讨四种常见的排序算法:选择排序、插入排序、快速排序以及冒泡排序,它们都是用C语言实现的。以下是这些排序算法的详细解析: 1. **选择排序(Selection Sort)** - 选择排序是一种简单直观的排序...
采用c++描述了各种排序算法,包括选择排序 冒泡排序 插入排序 基数排序 快速排序 归并排序 。实验内容 1、创建排序类。 2、提供操作:选择排序、冒泡排序、插入排序、*基数排序、*快速排序、*归并排序。 3、*能够...
本资源包含三个经典的排序算法的源代码:插入排序、选择排序和冒泡排序,这些都是初级到中级程序员常学习和使用的算法。下面将详细介绍这三个排序算法的工作原理、特点以及代码实现。 1. **插入排序(Insertion ...
5. 快速排序(Quick Sort):快速排序是一种分治策略的排序算法,通过选取一个“基准”元素,将数组分为两部分,一部分的所有元素都小于基准,另一部分的所有元素都大于基准,然后再对这两部分进行快速排序。...
本资源提供了七大经典排序算法的实现程序,包括快速排序、冒泡排序、选择排序、归并排序、插入排序、希尔排序和堆排序。下面将逐一详细介绍这些排序算法及其原理。 1. 快速排序:由C.A.R. Hoare提出,是一种采用...
将杂乱无章的数据元素,通过一定的方法按关键字顺序排列的过程叫做排序。...本资源通过matlab实现合并排序、简单选择排序、快速排序、冒泡排序、直接插入排序5种常用的排序算法,并部分绘制代表算法原理的动图。
数据结构---直接插入排序/快速排序/选择排序/冒泡排序(详细实现算法和性能比较)
以上六种排序算法各有优缺点,如选择排序和冒泡排序时间复杂度较高,但实现简单;插入排序在部分有序的情况下效率较高;基数排序适用于处理大量整数排序;快速排序平均性能优秀,但最坏情况下时间复杂度较高;归并...
直接插入排序、冒泡排序、快速排序、直接选择排序、堆排序和二路归并排序是计算机科学中经典的排序算法,它们在数据处理和算法学习中占有重要地位。这些排序算法各有特点,适用场景不同,下面将逐一详细介绍,并结合...
本话题主要探讨六种内部排序算法:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序以及堆排序。这六种排序算法各有优劣,适用于不同的场景,接下来我们将逐一进行详细阐述。 1. **直接插入排序**: 直接...
数据结构(c语言版)严蔚敏 吴伟民编著 中直接插入排序、折半排序、shell排序、冒泡排序、快速排序、选择排序、堆排序的实现、归并排序,使用c语言实现
经典排序算法 - 快速排序Quick sort 经典排序算法 - 桶排序Bucket sort 经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - ...
这里我们汇总了七种常见的排序算法:Shell排序、归并排序、选择排序、快速排序、堆排序、冒泡排序和插入排序。每种算法都有其独特的特点和适用场景,下面将逐一详细介绍。 1. **Shell排序**:由Donald Shell提出,...
总的来说,这段代码提供了四种排序算法的实现,分别是冒泡排序、选择排序、插入排序以及Java内置的数组排序。每种排序算法都有其适用场景,理解这些算法可以帮助我们更好地解决实际问题,并根据需求选择合适的排序...
因此,希尔排序首先对一定增量序列分组,对每组使用直接插入排序算法排序;然后不断地减小增量,重复前面的过程,直至整个序列有序。 **代码实现:** ```csharp public class ShellSorter { public void Sort(int...
排序算法汇总(选择排序、直接插入排序、冒泡排序、希尔排序、快速排序、堆排序) 本资源介绍了六种常用的排序算法:选择排序、直接插入排序、冒泡排序、希尔排序、快速排序和堆排序。下面对每种算法进行详细介绍:...