1.冒泡排序
基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。
每次循环将最大的元素放到数组最后
子循环第一次排序，将最大的数放到最后，第二次循环，将第二大的数放到倒数第二的位置...以此类推。（适合小数据量排序）
对数组int[] a = {12,2,45,23,9,88,33,23,22,5,4,4,5,1,9,7,2,7,8};按从小到大的顺序排列。
代码：
|
/** * 冒泡排序。从小到大排序。<br> * 基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。<br> * 子循环第一次排序，将最大的数放到最后，第二次循环，将第二大的数放到倒数第二的位置...以此类推。<br> * @param source * @return */ public static int[] bubbleSort(int[] source) {
for (int i = 1; i < source.length; i++) { for (int j = 0; j < source.length - i; j++) { if (source[j] > source[j+1]) { int temp = source[j]; source[j] = source[j+1]; source[j+1] = temp; } } // 输出每个子循环排序后的数组中的元素 printArray(source,i); } return source; }
/** * 循环输出数组中的元素。 * @param a * @param idx，第一层循环的index */ public static void printArray(int[] a,int idx) { for (int i = 0; i < a.length; i++) { System.out.print(a[i]); if (i != a.length - 1) { System.out.print(","); } } System.out.println("---" + idx); } |
看看输出的结果：
2,12,23,9,45,33,23,22,5,4,4,5,1,9,7,2,7,8,88---1
2,12,9,23,33,23,22,5,4,4,5,1,9,7,2,7,8,45,88---2
2,9,12,23,23,22,5,4,4,5,1,9,7,2,7,8,33,45,88---3
2,9,12,23,22,5,4,4,5,1,9,7,2,7,8,23,33,45,88---4
2,9,12,22,5,4,4,5,1,9,7,2,7,8,23,23,33,45,88---5
2,9,12,5,4,4,5,1,9,7,2,7,8,22,23,23,33,45,88---6
2,9,5,4,4,5,1,9,7,2,7,8,12,22,23,23,33,45,88---7
2,5,4,4,5,1,9,7,2,7,8,9,12,22,23,23,33,45,88---8
2,4,4,5,1,5,7,2,7,8,9,9,12,22,23,23,33,45,88---9
2,4,4,1,5,5,2,7,7,8,9,9,12,22,23,23,33,45,88---10
2,4,1,4,5,2,5,7,7,8,9,9,12,22,23,23,33,45,88---11
2,1,4,4,2,5,5,7,7,8,9,9,12,22,23,23,33,45,88---12
1,2,4,2,4,5,5,7,7,8,9,9,12,22,23,23,33,45,88---13
1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,45,88---14
1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,45,88---15
1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,45,88---16
1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,45,88---17
1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,45,88---18
从第1行到第14行，
第1行，取出原数组的最大数放到最后，即88被放到了数组最后位置。（内层循环中比较的元素是0-source.length-1，即第1次比较的是全部数组元素）。
第2行，从第一次排序后的结果中取出最大数放到最后（内层循环中比较的元素是0-source.length-2，即上面第1行标颜色的部分）
第3行，从第二次排序后的结果中取出最大的数放到最后（上面第二行标颜色的部分）。
…
依此类推，但是到了14行，即上面标黄的部分，那里就已经排序完毕了（也就是已经从小到大排序完了），那么后面几次的循环是没必要的。
那么如果解决这个问题呢？
改进的代码如下：
|
public static int[] bubbleSort(int[] source) { boolean isSort = false; // 是否排序
for (int i = 1; i < source.length; i++) { isSort = false; // 在每次排序前都初始化为false for (int j = 0; j < source.length - i; j++) { if (source[j] > source[j+1]) { int temp = source[j]; source[j] = source[j+1]; source[j+1] = temp;
isSort = true; // 为TRUE表明此次循环（外层循环）有排序。 } }
if (!isSort) break; // 如果没有排序，说明数据已经排序完毕。 // 输出每个子循环排序后的数组中的元素 printArray(source,i); } return source; } |
2.选择排序
原理：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。（适合小数据量排序）
代码：
|
/** * 原理：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 * 选择排序。从小到大排序 * @param source * @return */ public static int[] selectSort(int[] source) { int min_idx = -1; // 当此循环所有元素最小元素所在的下标。
for (int i = 0; i < source.length-1; i++) { min_idx = i; // 以i为界，将数组分为前后2部分。 for (int j = i+1; j < source.length; j++) { // i之后的数组元素 if (source[j] < source[min_idx]) { // 后面部分的数组中有元素小于前部分，循环取出最小的一个值的下标 min_idx = j; } } if (min_idx != i) { // 如果min_idx = i说明后面部分的数组没有元素值大于前面部分。否则将后面部分最小的元素移到前面。 int temp = source[i]; source[i] = source[min_idx]; source[min_idx] = temp; } printArray(source, i); }
return source; }
测试数据：int[] a = {12,2,45,23,9,88,33,23,22,5,4,4,5,1,9,7,2,7,8,0}; |
程序输出：
0,2,45,23,9,88,33,23,22,5,4,4,5,1,9,7,2,7,8,12---0
0,1,45,23,9,88,33,23,22,5,4,4,5,2,9,7,2,7,8,12---1
0,1,2,23,9,88,33,23,22,5,4,4,5,45,9,7,2,7,8,12---2
0,1,2,2,9,88,33,23,22,5,4,4,5,45,9,7,23,7,8,12---3
0,1,2,2,4,88,33,23,22,5,9,4,5,45,9,7,23,7,8,12---4
0,1,2,2,4,4,33,23,22,5,9,88,5,45,9,7,23,7,8,12---5
0,1,2,2,4,4,5,23,22,33,9,88,5,45,9,7,23,7,8,12---6
0,1,2,2,4,4,5,5,22,33,9,88,23,45,9,7,23,7,8,12---7
0,1,2,2,4,4,5,5,7,33,9,88,23,45,9,22,23,7,8,12---8
0,1,2,2,4,4,5,5,7,7,9,88,23,45,9,22,23,33,8,12---9
0,1,2,2,4,4,5,5,7,7,8,88,23,45,9,22,23,33,9,12---10
0,1,2,2,4,4,5,5,7,7,8,9,23,45,88,22,23,33,9,12---11
0,1,2,2,4,4,5,5,7,7,8,9,9,45,88,22,23,33,23,12---12
0,1,2,2,4,4,5,5,7,7,8,9,9,12,88,22,23,33,23,45---13
0,1,2,2,4,4,5,5,7,7,8,9,9,12,22,88,23,33,23,45---14
0,1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,88,33,23,45---15
0,1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,88,45---16
0,1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,88,45---17
0,1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,45,88---18
这是从小到大排序的结果，
第1次循环，取出数组中最小的元素放在数组第一个位置；
第2次循环，取出剩余待排序数组中最小的值1，放到待排序数组的第1位；
…
第1次循环，已经排好的元素：无；比较的元素，左边：12，右边：剩余元素。
第2次循环，已经排好的元素：0，不参与后面的排序；比较的元素，左边：2，右边：数组中除已经已经排好的元素和左边的元素之外的元素。
…
最后一次，已经排好的元素：0,1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33，不参与后面的排序；比较的元素，左边：88；右边：45。
上面标注颜色的部分是不参与下一次排序（或比较）的元素。
3.插入排序
每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。（适合小数据量排序）
代码：
|
/** * 插入排序，从小到大。 * @param source * @return */ public static int[] insertSort(int[] source) { for (int i = 1; i < source.length; i++) { int idx = i; int data = source[idx];
while ((idx > 0 && source[idx-1] > data)) { source[idx] = source[idx-1]; idx--; }
source[idx] = data; printArray(source, i); } return source; } 测试数据：int[] a = {12,2,45,23,9,88,33,23,22,5,4,4,5,1,9,7,2,7,8,0}; |
输出：
2,12,45,23,9,88,33,23,22,5,4,4,5,1,9,7,2,7,8,0---1—》12与2比较
2,12,45,23,9,88,33,23,22,5,4,4,5,1,9,7,2,7,8,0---2—》45与2，12比较
2,12,23,45,9,88,33,23,22,5,4,4,5,1,9,7,2,7,8,0---3—》23与2，12，45比较
2,9,12,23,45,88,33,23,22,5,4,4,5,1,9,7,2,7,8,0---4—》9与2，12，13，45比较
2,9,12,23,45,88,33,23,22,5,4,4,5,1,9,7,2,7,8,0---5—》88与2，9，12，23，45比较
2,9,12,23,33,45,88,23,22,5,4,4,5,1,9,7,2,7,8,0---6
2,9,12,23,23,33,45,88,22,5,4,4,5,1,9,7,2,7,8,0---7
2,9,12,22,23,23,33,45,88,5,4,4,5,1,9,7,2,7,8,0---8
2,5,9,12,22,23,23,33,45,88,4,4,5,1,9,7,2,7,8,0---9
2,4,5,9,12,22,23,23,33,45,88,4,5,1,9,7,2,7,8,0---10
2,4,4,5,9,12,22,23,23,33,45,88,5,1,9,7,2,7,8,0---11
2,4,4,5,5,9,12,22,23,23,33,45,88,1,9,7,2,7,8,0---12
1,2,4,4,5,5,9,12,22,23,23,33,45,88,9,7,2,7,8,0---13
1,2,4,4,5,5,9,9,12,22,23,23,33,45,88,7,2,7,8,0---14
1,2,4,4,5,5,7,9,9,12,22,23,23,33,45,88,2,7,8,0---15
1,2,2,4,4,5,5,7,9,9,12,22,23,23,33,45,88,7,8,0---16
1,2,2,4,4,5,5,7,7,9,9,12,22,23,23,33,45,88,8,0---17
1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,45,88,0---18
0,1,2,2,4,4,5,5,7,7,8,9,9,12,22,23,23,33,45,88---19
标黄的是排好序的，后面的是未排序的。用未排序的第1个元素与前面排好序的元素比较，确定未排序的第一个元素的插入位置。
4.快速排序
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。（适合大量数据排序）
|
/** * 快速排序。<br> * 思想：选定一个元素作为枢纽元素，将小于该元素的元素放到左边，大于该元素的放到右边。不断重复此过程。<br> * 直到最终形成一个有序的列表。<br> * 下面的参数low,high就是可以支持一个数组的一个子区间进行排序。<br> * 如果是整个数组进行排序，则low=0,high=数组.length-1。 * @param data:要排序的数组。 * @param low:排序的起始位置 * @param high:排序的结束位置。 */ public static void quicksort(int[] data,int low,int high) { int i=low,j=high;
if (low < high) { // 枢纽元素 int key = data[i]; System.out.println("枢纽元素是：" + key + ",low:" + low + ",high:" + high);
while (i < j) { // 从右往左判断，将小于枢纽元素的元素放到枢纽元素左边。 while (i < j && data[j] > key) { j--; }
if (i < j) { data[i] = data[j]; i++; }
// 从左往右判断，将大于枢纽元素的元素放到枢纽元素右边 while (i < j && data[i] < key) { i++; }
if (i < j) { data[j] = data[i]; j--; }
data[i] = key; }
printArray(data);
// 递归将枢纽元素左边的元素再分成2部分，将小于新枢纽元素的元素放到左边；大于新枢纽元素的元素放到右边。 quicksort(data,low,i-1); // 递归右边 quicksort(data,i+1,high); } } 测试： int[] a = { 12, 2, 45, 23, 9, 88, 33, 23, 22, 5, 4, 4, 5, 1, 9, 7, 2, 7, 8, 0 }; // 从第6个元素开始，看到第16个元素，即只对这一个范围内的元素进行排序（标黄的部分）。 quicksort(a, 5, 15); 排序过程： 枢纽元素是：88,low:5,high:15 12,2,45,23,9,7,33,23,22,5,4,4,5,1,9,88,2,7,8,0 枢纽元素是：7,low:5,high:14 12,2,45,23,9,1,5,4,4,5,7,22,23,33,9,88,2,7,8,0 枢纽元素是：1,low:5,high:9 12,2,45,23,9,1,5,4,4,5,7,22,23,33,9,88,2,7,8,0 枢纽元素是：5,low:6,high:9 12,2,45,23,9,1,5,4,4,5,7,22,23,33,9,88,2,7,8,0 枢纽元素是：5,low:6,high:8 12,2,45,23,9,1,4,4,5,5,7,22,23,33,9,88,2,7,8,0 枢纽元素是：4,low:6,high:7 12,2,45,23,9,1,4,4,5,5,7,22,23,33,9,88,2,7,8,0 枢纽元素是：22,low:11,high:14 12,2,45,23,9,1,4,4,5,5,7,9,22,33,23,88,2,7,8,0 枢纽元素是：33,low:13,high:14 12,2,45,23,9,1,4,4,5,5,7,9,22,23,33,88,2,7,8,0 标黄的部分即是排序的部分。 |
相关推荐
### Java 实现几种常见排序方法 #### 泡泡排序（Bubble Sort） 泡泡排序是一种简单的排序算法，它重复地遍历待排序的数列，依次比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复...
本篇文章将深入探讨数组的几种常见排序方法，包括冒泡排序、选择排序和插入排序，这些都是基础且实用的排序算法，对于理解更复杂的排序算法有着重要的铺垫作用。 ### 冒泡排序 冒泡排序是一种简单直观的排序算法。...
除了上述提及的排序算法之外，文档中还提到了希尔排序（Shell Sort）、基数排序（Radix Sort）、鸡尾酒排序（Cocktail Shaker Sort）、桶排序（Bucket Sort）和鸽巢排序（Bucket Sort）等多种排序方法。这些排序算法...
常见的几种排序方式，包括选择排序，冒泡排序，快速排序，希尔排序，堆排序，插入排序。vs2008实现，对话框方式，主要实现字符串的由小到大排序。点击“几种排序方法.vcproj“运行。字符集使用多字节集，不能用...
以上就是几种常见的排序算法，每种都有其适用场景和优缺点。在实际应用中，我们通常会根据数据规模、是否已经部分排序、内存限制等因素选择合适的排序算法。了解并掌握这些排序方法对于理解和优化算法性能至关重要。
Java中几种比较常见的排序方法，像冒泡、快速排序、插入排序登。
几种常见的排序算法是编程领域中基础且重要的知识点，它们各自有不同的特点和适用场景。本文将详细介绍这些算法，并分析其效率。 一、冒泡排序 冒泡排序是一种简单的排序算法，通过不断交换相邻的两个元素来逐步...
一些常用排序算法的C语言实现，包括直接选择排序，希尔排序，直接插入排序，快速排序，归并排序，冒泡排序，堆排序
这篇文章将详细介绍JavaScript中几种常见的排序方法，帮助你更好地理解和运用这些技术。 首先，最基本的排序方法是`Array.prototype.sort()`。这个内置函数可以接受一个比较函数作为参数，用于自定义排序规则。例如...
本文将深入探讨几种常见的数字排序方法，包括直接插入法、Shell排序、冒泡排序、快速排序以及选择排序。这些排序方法各有特点，适用于不同的场景，理解并掌握它们对于提升编程技能至关重要。 **1. 直接插入排序...
根据提供的文件信息，本文将详细介绍如何使用Java语言来实现几种常见的排序算法，包括插入排序（Insert Sort）、冒泡排序（Bubble Sort）、选择排序（Selection Sort）以及希尔排序（Shell Sort）。这些排序算法在...
位与运算不会改变元素的相对顺序，通常不用于通用排序，但在特定问题（如按某几位进行排序）中可能会派上用场。在VC6.0中，实现位与排序可能需要自定义比较函数，确保正确排序。 2. **选择排序**： 选择排序是一种...
本资料主要探讨了四种常见的排序算法，它们分别是冒泡排序、选择排序、插入排序和快速排序。下面将对这些算法进行详细解释。 ### 1. 冒泡排序（Bubble Sort） 冒泡排序是一种简单直观的排序算法，它重复地遍历要...
数据结构中几种常见的排序算法之比较，比较常见的冒泡排序、快速排序等
设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 在本文中，我们将设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数，以取得直观感受。内部排序算法是指在内存中...
几种常见排序 基于比较的排序算法: 下界是 nlgn 1.1 SelectionSort：每次选出最下的元素，放在当前循环最左边的位置。 1.2 BubbleSort：每次比较相邻的两个数，使得最大的数像气泡一样冒到最右边。 1. 3 Insertion...
这里我们将深入探讨几种最常见的排序算法，包括冒泡排序、选择排序、插入排序、快速排序以及归并排序。 1. 冒泡排序（Bubble Sort） 冒泡排序是最基础的排序算法之一，它通过不断地比较相邻元素并交换位置来实现...