已经好久没写算法了,脑袋都生锈了。。
首先排序分为四种:
交换排序: 包括冒泡排序,快速排序。
选择排序: 包括直接选择排序,堆排序。
插入排序: 包括直接插入排序,希尔排序。
合并排序: 合并排序。
本篇对交换排序进行研究。
1、冒泡排序
- 比较相邻的前后二个数据,如果前面数据大于后面的数据,就将二个数据交换。
- 这样对数组的第0个数据到N-1个数据进行一次遍历后,最大的一个数据就“沉”到数组第N-1个位置。
- N=N-1,如果N不为0就重复前面二步,否则排序完成。
精髓:相邻之间相比较交换
public static void bubbleSort(int arr[]){ for(int i=0;i<arr.length;i++){//1.外层循环 for(int j=0;j<arr.length-1-i;j++){//2.内层循环 if(arr[j]>arr[j+1]){//3.逐个比较,大于则交换 int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }
2、快速排序
快速排序采用的思想是分治思想。
快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值,如此作为基准的元素调整到排序后的正确位置。递归快速排序,将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置,排序完成。所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。
- 记录排序数组左边坐标,当前排序数组右边坐标,取左边的一个数据当作基点(把这个点挖出一个坑)
- 从右边往左边找,找到一个比base小的数据,把从右边找到的小于base的数据填到左边挖出的坑
- 从左往右边找,找到一个比base大的数据,把从左边找到的大于base的数据填到右边挖出的坑
- 把base填到最后剩下的坑
- 对依赖base排好序数组的左边的数组排序
- 对依赖base排好序数组的右边的数组排序
太抽象了。。。
还是举例子来说明吧
(1)、left=0,right=5,base=50;//首先记录左边的坐标,右边的坐标,取第一个数据做为基准。可以理解数组[0]已经被挖坑了。
0
|
1
|
2
|
3
|
4
|
5
|
50
|
20
|
10 |
70
|
30
|
60
|
(2)、从右往左找,找到一个比基准50小的数据,数据是30,此时数组[0]=30,被填坑,数组[4]被挖坑。right坐标移到4,left还是为0。
0
|
1
|
2
|
3
|
4
|
5
|
30
|
20
|
10 |
70
|
30
|
60
|
0
|
1
|
2
|
3
|
4
|
5
|
30
|
20
|
10 |
70
|
70
|
60
|
0
|
1
|
2
|
3
|
4
|
5
|
30
|
20
|
10 |
50
|
70
|
60
|
代码如下:
public static void quickSort(int array[],int sortArrayLeft,int sortArrayRight){ if(sortArrayLeft>=sortArrayRight){ return; } int left = sortArrayLeft; //1.1、当前排序数组左边坐标 int right = sortArrayRight; //1.2、当前排序数组右边坐标 int base = array[left]; //1.3、取左边的一个数据当作基点 while(left<right){ while(left<right && array[right]>=base){//2、从右边往左边找,找到一个比base小的数据 right --; } array[left] = array[right];//3、把从右边找到的小于base的数据填到左边挖出的坑 while(left <right && array[left] <= base){//4、从左往右边找,找到一个比base大的数据 left ++; } array[right] = array[left];//5、把从左边找到的大于base的数据填到右边挖出的坑 } array[left] = base;//6、把base填到最后剩下的坑 quickSort(array, sortArrayLeft, left-1);//7、对依赖base排好序数组的左边的数组排序 quickSort(array, left+1, sortArrayRight);//8、对依赖base排好序数组的右边的数组排序 }
相关推荐
本篇文章主要探讨了如何在VC++环境中利用多线程技术来实现三种经典的排序算法:冒泡排序、快速排序和归并排序,并对它们的性能进行了比较。 首先,冒泡排序是一种简单的排序算法,它重复地遍历待排序的数列,一次...
在实际应用中,冒泡排序效率较低,时间复杂度为O(n^2),对于大数据量或性能要求高的场景,通常会选择其他更高效的排序算法,如快速排序、归并排序或堆排序等。然而,由于其简单易懂,冒泡排序在教学和理解排序算法...
冒泡排序是一种基础且经典的排序算法,它的基本思想是通过不断地交换相邻的逆序元素,使得每一轮排序后,最大的元素“浮”到数组的末尾。这个过程就像水底下的气泡逐渐升至水面一样,因此得名“冒泡排序”。 在Java...
本篇文章将详细讨论几种常见的排序算法:选择排序、冒泡排序、插入排序、合并排序以及快速排序,分析它们的算法原理、时间效率,并通过经验分析验证理论分析的准确性。 **1. 选择排序(Selection Sort)** 选择排序...
快速排序和冒泡排序是两种常见的排序算法,它们在计算机科学中扮演着重要的角色,特别是在数据处理和优化程序性能方面。本篇文章将深入探讨这两种排序算法的原理、效率以及它们在C#编程语言中的实现。 首先,让我们...
本主题将详细探讨四种常见的排序算法:选择排序、插入排序、快速排序以及冒泡排序,它们都是用C语言实现的。以下是这些排序算法的详细解析: 1. **选择排序(Selection Sort)** - 选择排序是一种简单直观的排序...
本文将深入探讨四种在C++中实现的常见排序算法:插入排序、冒泡排序、堆排序和快速排序。这些算法各有特点,适用于不同的场景,理解并掌握它们对于提升编程能力至关重要。 1. **插入排序**: 插入排序是一种简单的...
1.冒泡排序算法 冒泡排序算法是一种简单的排序算法,它的工作原理是通过不断地比较相邻元素,并交换它们以达到排序的目的。冒泡排序算法的时间复杂度为O(n^2),因此它适合小规模的数据排序。 2.选择排序算法 选择...
将杂乱无章的数据元素,通过一定的方法按关键字顺序排列的过程叫做排序。...本资源通过matlab实现合并排序、简单选择排序、快速排序、冒泡排序、直接插入排序5种常用的排序算法,并部分绘制代表算法原理的动图。
同时,我们也可以对本课程学习的意见建议,即快速排序是由冒泡排序改进而得的,所以一定要熟练掌握冒泡排序,才能更好的理解快速排序。 快速排序算法是一种重要的排序算法,它具有排序速度快、就地排序的优点,但也...
这七种算法分别是:冒泡排序、选择排序、直接插入排序、希尔排序、堆排序、归并排序和快速排序。 1. **冒泡排序**: 冒泡排序是最基础的排序算法之一,通过重复遍历待排序序列,比较相邻元素并交换位置来实现排序...
冒泡排序的时间复杂度同样为O(n²),并且在最好情况下(即数据已经有序)只需进行n-1次比较即可完成排序。 这些排序算法各有优缺点,适用于不同的场景。在实际应用中,通常会选择时间复杂度更低的排序算法,如快速...
根据给定的信息,本文将详细解释C#中的几种基本排序算法:选择排序、冒泡排序、快速排序、插入排序、希尔排序以及归并排序的基本原理和实现方式。 ### 一、选择排序(Selection Sort) #### 算法原理 选择排序是一...
各类排序算法整理--C语言描述--本人编写 排序算法种类有: 冒泡 快速排序 堆排序 希尔排序 插入排序 选择排序 二路归并排序
本资源提供了七大经典排序算法的实现程序,包括快速排序、冒泡排序、选择排序、归并排序、插入排序、希尔排序和堆排序。下面将逐一详细介绍这些排序算法及其原理。 1. 快速排序:由C.A.R. Hoare提出,是一种采用...
| 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 | | 简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 稳定 | | 直接插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 | | 希尔排序 | O(nlogn)~O(n^2) | O(n...
经典排序算法 - 快速排序Quick sort 经典排序算法 - 桶排序Bucket sort 经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - ...
本话题主要探讨六种内部排序算法:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序以及堆排序。这六种排序算法各有优劣,适用于不同的场景,接下来我们将逐一进行详细阐述。 1. **直接插入排序**: 直接...
本文将深入探讨标题和描述中提到的一些基本排序算法,包括选择排序、冒泡排序、插入排序、希尔排序、堆排序、快速排序以及归并排序,并结合C++编程语言进行讲解。 1. **选择排序(Selection Sort)** - 选择排序是一...