排序概念:
1.内部排序:
工具类中定义交换数组元素、生成数据源等方法(用于下面的排序):
import java.util.Random; public class SortUtil { // 通过数组下标交换元素位置 public static void swap(int[] data, int i, int j) { int temp = data[i]; data[i] = data[j]; data[j] = temp; } // 生成and显示数据源 public static void DataSrc(int[] is) { for (int i = 0; i < is.length; i++) { is[i] = new Random().nextInt(100); } System.out.print("源数据:\t"); for (int i = 0; i < is.length; i++) { System.out.print(+is[i] + " "); } System.out.println(); } // 显示最终排序结果 public static void showRes(int[] is) { System.out.print("排序结果:\t"); for (int i = 0; i < is.length; i++) { System.out.print(+is[i] + " "); } } // 显示每此排序后的情况 public static void showEach(int[] is, int i) { System.out.print("第" + (i + 1) + "次排序:\t"); for (int k = 0; k < is.length; k++) { System.out.print(is[k] + " "); } System.out.println(); } }
1.1冒泡排序:
冒泡排序的基本思想是:对待排序记录关键字从后往前(逆序)进行多遍扫描,当发现相邻两个关键字的次序与排序要求的规则不符时,就将这两个数据进行交换,这样,关键字较小的记录将逐渐从后往前移动,就像气泡在水中 向上浮一样,所以该算法也称为气泡排序法.
冒泡排序图解:
代码实现:
public class BubbleSort { public static void main(String[] args) { int[] is = new int[10]; // 在工具类生成10个100以内随机数作为数据源并显示 SortUtil.DataSrc(is); for (int i = 0; i < is.length - 1; i++) { for (int j = 0; j < is.length - i - 1; j++) { if (is[j] > is[j + 1]) { SortUtil.swap(is, j, j + 1);// 通过下标对两个数进行位置交换 } } // 显示每一次排序的结果 SortUtil.showEach(is, i); } // 显示最终排序结果 SortUtil.showRes(is); } }
排序结果及过程:
1.2快速排序:
快速排序使用分支策略来把排序元素序列分为两个子序列,具体步骤为:
(1):从数列中挑出一个元素,该元素称为"基准".
(2):扫描一遍数列,将所有比"基准"小的元素排在基准前面,所有比"基准"大的元素排在"基准"后面.
(3):通过递归,将各个子序列划分为更小的序列,直到把小于"基准"元素的子数列和大于基准元素的子序列排序.
快速排诉步骤:
快速排序实现:
public class QuickSort { public static void main(String[] args) { int[] is = new int[10]; SortUtil.DataSrc(is); quickSort(is, 0, is.length-1); SortUtil.showRes(is); } private static void quickSort(int[] data, int i, int j) { int pivotIndex = (i + j) / 2; SortUtil.swap(data, pivotIndex, j); int k = partition(data, i - 1, j, data[j]); SortUtil.swap(data, k, j); if ((k - i) > 1) quickSort(data, i, k - 1); if ((j - k) > 1) quickSort(data, k + 1, j); } private static int partition(int[] data, int l, int r, int pivot) { do { while (data[++l] < pivot) ; while ((r != 0) && data[--r] > pivot) ; SortUtil.swap(data, l, r); } while (l < r); SortUtil.swap(data, l, r); return l; } }
快速排序结果:
--------------------------------------------------------
1.3简单选择排序:
选择排序的基本思想:对n个记录进行扫描,选择最小的记录,将其输出,接着在剩下的n-1个记录中进行扫描,选择最小的记录将其输出,...不断重复这个过程,直到只剩一个记录为止.
简单选择排序:
简单选择排序实现:
public class SelectionSort { public static void main(String[] args) throws Exception { int[] is = new int[10]; SortUtil.DataSrc(is); sort(is); SortUtil.showRes(is); } private static void sort(int[] is) { for (int i = 0; i < is.length - 1; i++) { for (int j = i + 1; j < is.length; j++) { if (is[i] > is[j]) { SortUtil.swap(is, i, j); } } SortUtil.showEach(is, i); } } }
运行结果:
1.4 堆排序
堆排序是一个完全二叉树,树中的每个结点对应于原始数据的一个记录,并且每个结点应该满足以下条件:非叶结点的数据大于或等于其左、右孩子的
数据(若是按照从小到大的顺序排序,则要求非叶结点的数据小于或等于其左、右孩子结点的数据).
由堆的定义可以看出,其根结点为最大值,堆排序就是利用这一特点进行的,堆排序的过程包括两个阶段:
(1):将无序的数据构成堆(即用无序数据生成满足堆定义的完全二叉树).
(2):利用堆排序(用上一步生成的堆生成有序的数据,实际上就是对完全二叉树进行遍历).
例子:69,65,90,37,92,6,28,54:
树的生成过程:
堆排序输出过程(每生成一个数后要树的结构改变,要重新生成一次):
堆排序实现:
public class DeapSort { public static void main(String[] args) { int[] is = new int[10]; SortUtil.DataSrc(is); sort(is); SortUtil.showRes(is); } public static void sort(int[] data) { MaxHeap h = new MaxHeap(); h.init(data); for (int i = 0; i < data.length; i++) h.remove(); System.arraycopy(h.queue, 1, data, 0, data.length); } private static class MaxHeap { private int size = 0; private int[] queue; void init(int[] data) { this.queue = new int[data.length + 1]; for (int i = 0; i < data.length; i++) { queue[++size] = data[i]; fixUp(size); } } public void remove() { SortUtil.swap(queue, 1, size--); fixDown(1); } // fixdown private void fixDown(int k) { int j; while ((j = k << 1) <= size) { if (j < size && queue[j] < queue[j + 1]) j++; if (queue[k] > queue[j]) // 不用交换 break; SortUtil.swap(queue, j, k); k = j; } } private void fixUp(int k) { while (k > 1) { int j = k >> 1; if (queue[j] > queue[k]) break; SortUtil.swap(queue, j, k); k = j; } } } }
1.5 直接插入排序法:
插入排序(InsertionSort)的算法描述是一种简单直观的排序算法.它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应的位置并插入.插入排序在实现上,在从后向前扫描的过程中,需要反复把已经排序的元素逐步向后移动,为最新元素提供插入空间.
直接插入排序:
直接插入排序实现:
public class InsertSort { public static void main(String[] args) { int[] is = new int[10]; SortUtil.DataSrc(is); sort(is); SortUtil.showRes(is); } private static void sort(int[] is) { for (int i = 1; i < is.length; i++) {// 默认只有一个元素时是有序的,所以不用排序 for (int j = i; j > 0; j--) { if (is[j] < is[j - 1]) SortUtil.swap(is, j, j - 1); } } } }
1.6希尔排序:
希尔排序又称为缩小增量排序,也属于插入排序类的算法,是对直接插入排序的一种改进.
基本思想就是:将需要排序的序列划分为若干个较小的序列,对这些序列 进行直接插入排序,通过这样的操作可使用需要排列的数列基本有序,最后再使用一次直接插入排序,这样,首先对数量较小的序列进行直接插入排序可提高效率,最后对基本有序的序列进行直接插入排序,也可提高效率,排序过程的效率得到提升.
希尔排序过程图解:
希尔排序实现:
public class ShellSort { public static void main(String[] args) { int[] is = new int[10]; SortUtil.DataSrc(is); sort(is); SortUtil.showRes(is); } public static void sort(int[] data) { for (int i = data.length / 2; i > 2; i /= 2) { for (int j = 0; j < i; j++) { insertSort(data, j, i); } } insertSort(data, 0, 1); } private static void insertSort(int[] data, int start, int inc) { for (int i = start + inc; i < data.length; i += inc) { for (int j = i; (j >= inc) && (data[j] < data[j - inc]); j -= inc) { SortUtil.swap(data, j, j - inc); } } } }
1.7合并排序(MergeSort):
就是将两个或多个有序表合并成一个有序表.
合并排序图解:
合并排序实现:
public class MergeSort { public static void main(String[] args) { int[] is = new int[10]; SortUtil.DataSrc(is); sort(is); SortUtil.showRes(is); } public static void sort(int[] data) { int[] temp = new int[data.length]; mergeSort(data, temp, 0, data.length - 1); } private static void mergeSort(int[] data, int[] temp, int l, int r) { int mid = (l + r) / 2; if (l == r) return; mergeSort(data, temp, l, mid); mergeSort(data, temp, mid + 1, r); for (int i = l; i <= r; i++) { temp[i] = data[i]; } int i1 = l; int i2 = mid + 1; for (int cur = l; cur <= r; cur++) { if (i1 == mid + 1) data[cur] = temp[i2++]; else if (i2 > r) data[cur] = temp[i1++]; else if (temp[i1] < temp[i2]) data[cur] = temp[i1++]; else data[cur] = temp[i2++]; } } }
2.外部排序:
外部排序指的是大文件的排序,当待排序的文件很大时,无法将整个文件的所有记录同时调入内存进行排序,只能将文件存放在外存,这种排称为外部排序。外部排序的过程主要是依据数据的内外存交换和“内部归并”两者结合起来实现的。
相关推荐
常见排序算法的实现 (插入排序、shell排序、堆排序、冒泡排序、快速排序、归并排序)
提供了Java实现几种常见排序方法和原理介绍
交换排序 插入排序 选择排序 堆排序 归并排序 比较统计排序 分布统计排序
详细讲述了8中常见算法的原理及思想,并用JAVA进行了实现,代码中有详细的注释,解释了算法的实现逻辑和一些小技巧。
五种常见排序法的比较 归并排序 快速排序 选择排序 插入排序 冒泡排序
常见排序算法的实现与性能比较JAVA 问题描述:实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法 实验要求: A. 在随机产生的空间大小分别为 N = 10, 1000,10000,100000 的排序样本(取值为[0...
几种常见排序 基于比较的排序算法: 下界是 nlgn 1.1 SelectionSort:每次选出最下的元素,放在当前循环最左边的位置。 1.2 BubbleSort:每次比较相邻的两个数,使得最大的数像气泡一样冒到最右边。 1. 3 Insertion...
包含了最常见的七种排序的动态演示,均为gif格式的,方便查看,也方便在制作课件的时候插入到课件当中,以便于给学生演示排序过程。 冒泡排序、插入排序、选择排序、快速排序、希尔排序、归并排序、堆排序。
冒泡排序等7种常见排序源代码
以下是用Python实现的五种常见排序算法: 1. 冒泡排序(Bubble Sort): ```python def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+...
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法
Java实现的常见排序算法.pdfJava实现的常见排序算法.pdfJava实现的常见排序算法.pdfJava实现的常见排序算法.pdfJava实现的常见排序算法.pdfJava实现的常见排序算法.pdf
常见排序算法的实现(一)-插入排序 常见排序算法的实现(二)-shell排序 常见排序算法的实现(三)-堆排序 常见排序算法的实现(四)-冒泡排序 常见排序算法的实现(五)-快速排序 常见排序算法的实现(六)→归并排序
C语言实现常见排序算法。编译环境:VS2010。 包括: 冒泡排序 快速排序 直接插入排序 Shell排序 直接选择排序 堆排序 归并排序(递归和非递归两种) 桶式排序 基数排序:顺序和静态队列两种方法 索引排序(采用简单...
Java数据挖掘18大算法实现和10大常见排序算法以及其他相关经典DM算法集合。 18大数据挖掘的经典算法以及代码实现,涉及到了决策分类,聚类,链接挖掘,关联挖掘,模式挖掘等等方面,后面都是相应算法的文章,希望能够...
关于常见排序,冒泡法,插入排序,选择排序,快速排序等。C/C++语言 关于常见排序,冒泡法,插入排序,选择排序,快速排序等。C/C++语言 关于常见排序,冒泡法,插入排序,选择排序,快速排序等。C/C++语言 关于常见...
c++实现常见排序的模板:快排 堆排 折半 冒泡 选择 希尔 插入排序 可选择排序的数量 最终输出各种排序耗时
常见排序算法(JS版)