- 浏览: 48962 次
- 性别:
- 来自: 北京
文章分类
最新评论
- package sort;
- import java.util.Random;
- /**
- * 排序测试类
- *
- * 排序算法的分类如下: 1.插入排序(直接插入排序、折半插入排序、希尔排序); 2.交换排序(冒泡泡排序、快速排序);
- * 3.选择排序(直接选择排序、堆排序); 4.归并排序; 5.基数排序。
- *
- * 关于排序方法的选择: (1)若n较小(如n≤50),可采用直接插入或直接选择排序。
- * 当记录规模较小时,直接插入排序较好;否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜。
- * (2)若文件初始状态基本有序(指正序),则应选用直接插人、冒泡或随机的快速排序为宜;
- * (3)若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或归并排序。
- *
- */
- /**
- * @corporation 北京环亚
- * @author HDS
- * @date Nov 19, 2009 10:43:44 AM
- * @path sort
- * @description JAVA排序汇总
- */
- public class SortTest {
- // //////==============================产生随机数==============================///////////////////
- /**
- * @description 生成随机数
- * @date Nov 19, 2009
- * @author HDS
- * @return int[]
- */
- public int[] createArray() {
- Random random = new Random();
- int[] array = new int[10];
- for (int i = 0; i < 10; i++) {
- array[i] = random.nextInt(100) - random.nextInt(100);// 生成两个随机数相减,保证生成的数中有负数
- }
- System.out.println("==========原始序列==========");
- printArray(array);
- return array;
- }
- /**
- * @description 打印出随机数
- * @date Nov 19, 2009
- * @author HDS
- * @param data
- */
- public void printArray(int[] data) {
- for (int i : data) {
- System.out.print(i + " ");
- }
- System.out.println();
- }
- /**
- * @description 交换相邻两个数
- * @date Nov 19, 2009
- * @author HDS
- * @param data
- * @param x
- * @param y
- */
- public void swap(int[] data, int x, int y) {
- int temp = data[x];
- data[x] = data[y];
- data[y] = temp;
- }
- /**
- * 冒泡排序----交换排序的一种
- * 方法:相邻两元素进行比较,如有需要则进行交换,每完成一次循环就将最大元素排在最后(如从小到大排序),下一次循环是将其他的数进行类似操作。
- * 性能:比较次数O(n^2),n^2/2;交换次数O(n^2),n^2/4
- *
- * @param data
- * 要排序的数组
- * @param sortType
- * 排序类型
- * @return
- */
- public void bubbleSort(int[] data, String sortType) {
- if (sortType.equals("asc")) { // 正排序,从小排到大
- // 比较的轮数
- for (int i = 1; i < data.length; i++) { // 数组有多长,轮数就有多长
- // 将相邻两个数进行比较,较大的数往后冒泡
- for (int j = 0; j < data.length - i; j++) {// 每一轮下来会将比较的次数减少
- if (data[j] > data[j + 1]) {
- // 交换相邻两个数
- swap(data, j, j + 1);
- }
- }
- }
- } else if (sortType.equals("desc")) { // 倒排序,从大排到小
- // 比较的轮数
- for (int i = 1; i < data.length; i++) {
- // 将相邻两个数进行比较,较大的数往后冒泡
- for (int j = 0; j < data.length - i; j++) {
- if (data[j] < data[j + 1]) {
- // 交换相邻两个数
- swap(data, j, j + 1);
- }
- }
- }
- } else {
- System.out.println("您输入的排序类型错误!");
- }
- printArray(data);// 输出冒泡排序后的数组值
- }
- /**
- * 直接选择排序法----选择排序的一种 方法:每一趟从待排序的数据元素中选出最小(或最大)的一个元素,
- * 顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 性能:比较次数O(n^2),n^2/2 交换次数O(n),n
- * 交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CUP时间多,所以选择排序比冒泡排序快。
- * 但是N比较大时,比较所需的CPU时间占主要地位,所以这时的性能和冒泡排序差不太多,但毫无疑问肯定要快些。
- *
- * @param data
- * 要排序的数组
- * @param sortType
- * 排序类型
- * @return
- */
- public void selectSort(int[] data, String sortType) {
- if (sortType.endsWith("asc")) {// 正排序,从小排到大
- int index;
- for (int i = 1; i < data.length; i++) {
- index = 0;
- for (int j = 1; j <= data.length - i; j++) {
- if (data[j] > data[index]) {
- index = j;
- }
- }
- // 交换在位置data.length-i和index(最大值)两个数
- swap(data, data.length - i, index);
- }
- } else if (sortType.equals("desc")) { // 倒排序,从大排到小
- int index;
- for (int i = 1; i < data.length; i++) {
- index = 0;
- for (int j = 1; j <= data.length - i; j++) {
- if (data[j] < data[index]) {
- index = j;
- }
- }
- // 交换在位置data.length-i和index(最大值)两个数
- swap(data, data.length - i, index);
- }
- } else {
- System.out.println("您输入的排序类型错误!");
- }
- printArray(data);// 输出直接选择排序后的数组值
- }
- /**
- * 插入排序 方法:将一个记录插入到已排好序的有序表(有可能是空表)中,从而得到一个新的记录数增1的有序表。 性能:比较次数O(n^2),n^2/4
- * 复制次数O(n),n^2/4 比较次数是前两者的一般,而复制所需的CPU时间较交换少,所以性能上比冒泡排序提高一倍多,而比选择排序也要快。
- *
- * @param data
- * 要排序的数组
- * @param sortType
- * 排序类型
- */
- public void insertSort(int[] data, String sortType) {
- if (sortType.equals("asc")) { // 正排序,从小排到大
- // 比较的轮数
- for (int i = 1; i < data.length; i++) {
- // 保证前i+1个数排好序
- for (int j = 0; j < i; j++) {
- if (data[j] > data[i]) {
- // 交换在位置j和i两个数
- swap(data, i, j);
- }
- }
- }
- } else if (sortType.equals("desc")) { // 倒排序,从大排到小
- // 比较的轮数
- for (int i = 1; i < data.length; i++) {
- // 保证前i+1个数排好序
- for (int j = 0; j < i; j++) {
- if (data[j] < data[i]) {
- // 交换在位置j和i两个数
- swap(data, i, j);
- }
- }
- }
- } else {
- System.out.println("您输入的排序类型错误!");
- }
- printArray(data);// 输出插入排序后的数组值
- }
- /**
- * 反转数组的方法
- *
- * @param data
- * 源数组
- */
- public void reverse(int[] data) {
- int length = data.length;
- int temp = 0;// 临时变量
- for (int i = 0; i < length / 2; i++) {
- temp = data[i];
- data[i] = data[length - 1 - i];
- data[length - 1 - i] = temp;
- }
- printArray(data);// 输出到转后数组的值
- }
- /**
- * 快速排序 快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。 步骤为:
- * 1. 从数列中挑出一个元素,称为 "基准"(pivot), 2.
- * 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。
- * 3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
- * 递回的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递回下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
- *
- * @param data
- * 待排序的数组
- * @param low
- * @param high
- * @see SortTest#qsort(int[], int, int)
- * @see SortTest#qsort_desc(int[], int, int)
- */
- public void quickSort(int[] data, String sortType) {
- if (sortType.equals("asc")) { // 正排序,从小排到大
- qsort_asc(data, 0, data.length - 1);
- } else if (sortType.equals("desc")) { // 倒排序,从大排到小
- qsort_desc(data, 0, data.length - 1);
- } else {
- System.out.println("您输入的排序类型错误!");
- }
- }
- /**
- * 快速排序的具体实现,排正序
- *
- * @param data
- * @param low
- * @param high
- */
- private void qsort_asc(int data[], int low, int high) {
- int i, j, x;
- if (low < high) { // 这个条件用来结束递归
- i = low;
- j = high;
- x = data[i];
- while (i < j) {
- while (i < j && data[j] > x) {
- j--; // 从右向左找第一个小于x的数
- }
- if (i < j) {
- data[i] = data[j];
- i++;
- }
- while (i < j && data[i] < x) {
- i++; // 从左向右找第一个大于x的数
- }
- if (i < j) {
- data[j] = data[i];
- j--;
- }
- }
- data[i] = x;
- qsort_asc(data, low, i - 1);
- qsort_asc(data, i + 1, high);
- }
- }
- /**
- * 快速排序的具体实现,排倒序
- *
- * @param data
- * @param low
- * @param high
- */
- private void qsort_desc(int data[], int low, int high) {
- int i, j, x;
- if (low < high) { // 这个条件用来结束递归
- i = low;
- j = high;
- x = data[i];
- while (i < j) {
- while (i < j && data[j] < x) {
- j--; // 从右向左找第一个小于x的数
- }
- if (i < j) {
- data[i] = data[j];
- i++;
- }
- while (i < j && data[i] > x) {
- i++; // 从左向右找第一个大于x的数
- }
- if (i < j) {
- data[j] = data[i];
- j--;
- }
- }
- data[i] = x;
- qsort_desc(data, low, i - 1);
- qsort_desc(data, i + 1, high);
- }
- }
- /**
- * 二分查找特定整数在整型数组中的位置(递归) 查找线性表必须是有序列表
- *
- * @paramdataset
- * @paramdata
- * @parambeginIndex
- * @paramendIndex
- * @returnindex
- */
- public int binarySearch(int[] dataset, int data, int beginIndex,
- int endIndex) {
- int midIndex = (beginIndex + endIndex) >>> 1; // 相当于mid = (low + high)
- // / 2,但是效率会高些
- if (data < dataset[beginIndex] || data > dataset[endIndex]
- || beginIndex > endIndex)
- return -1;
- if (data < dataset[midIndex]) {
- return binarySearch(dataset, data, beginIndex, midIndex - 1);
- } else if (data > dataset[midIndex]) {
- return binarySearch(dataset, data, midIndex + 1, endIndex);
- } else {
- return midIndex;
- }
- }
- /**
- * 二分查找特定整数在整型数组中的位置(非递归) 查找线性表必须是有序列表
- *
- * @paramdataset
- * @paramdata
- * @returnindex
- */
- public int binarySearch(int[] dataset, int data) {
- int beginIndex = 0;
- int endIndex = dataset.length - 1;
- int midIndex = -1;
- if (data < dataset[beginIndex] || data > dataset[endIndex]
- || beginIndex > endIndex)
- return -1;
- while (beginIndex <= endIndex) {
- midIndex = (beginIndex + endIndex) >>> 1; // 相当于midIndex =
- // (beginIndex +
- // endIndex) / 2,但是效率会高些
- if (data < dataset[midIndex]) {
- endIndex = midIndex - 1;
- } else if (data > dataset[midIndex]) {
- beginIndex = midIndex + 1;
- } else {
- return midIndex;
- }
- }
- return -1;
- }
- // /////////////////////===================================测试====================//////////////////
- public static void main(String[] args) {
- SortTest ST = new SortTest();
- int[] array = ST.createArray();
- System.out.println("==========冒泡排序后(正序)==========");
- ST.bubbleSort(array, "asc");
- System.out.println("==========冒泡排序后(倒序)==========");
- ST.bubbleSort(array, "desc");
- array = ST.createArray();
- System.out.println("==========选择排序后(正序)==========");
- ST.selectSort(array, "asc");
- System.out.println("==========选择排序后(倒序)==========");
- ST.selectSort(array, "desc");
- array = ST.createArray();
- System.out.println("==========插入排序后(正序)==========");
- ST.insertSort(array, "asc");
- System.out.println("==========插入排序后(倒序)==========");
- ST.insertSort(array, "desc");
- array = ST.createArray();
- System.out.println("==========快速排序后(正序)==========");
- ST.quickSort(array, "asc");
- ST.printArray(array);
- System.out.println("==========快速排序后(倒序)==========");
- ST.quickSort(array, "desc");
- ST.printArray(array);
- System.out.println("==========数组二分查找==========");
- System.out.println("您要找的数在第" + ST.binarySearch(array, 74)+ "个位子。(下标从0计算)");
- }
- }
参考文献:http://www.blogjava.net/yaozhongping/archive/2009/11/18/302832.html
相关推荐
在本系统中,我们主要实现了五种常用的排序算法:冒泡排序法、快速排序法、直接插入排序法、折半插入排序法和树形选择排序法。这些算法都是在计算机科学中最基本和最重要的排序算法,广泛应用于各种数据处理和分析...
常见的经典排序算法有希尔排序、二分插入法、直接插入法、带哨兵的直接排序法、冒泡排序、选择排序、快速排序、堆排序等。 一、希尔排序(Shell 排序法) 希尔排序法,又称宿小增量排序,是 1959 年由 D.L.Shell ...
常见的排序算法有插入排序、快速排序、选择堆积排序法等。 插入排序算法是一种简单的排序算法,适用于小规模的数据结构。该算法将数据结构分成已排序部分和未排序部分,并将未排序部分的元素插入到已排序部分中。...
在计算机科学领域,排序算法是数据处理中的核心部分,它涉及到如何有效地重新排列一组数据,使其按照特定的顺序排列。本资源"总结了各种排序算法,并用C++代码实现,并有演示",提供了丰富的学习材料,包括不同类型...
希尔排序是一种基于插入排序的算法,通过将待排序的数组元素按某个增量分组,然后对每组使用直接插入排序算法排序。随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止...
本篇文章将介绍一种经典的排序算法——**合并排序法**(Merge Sort),并通过C语言实现该算法。合并排序是一种非常有效的排序方法,其核心思想是分治法:将数据分为若干个子集,对这些子集分别进行排序,最后将排序...
最快的排序算法 最快的内部排序法—桶排序法,排序算法数据结构
在IT领域,排序算法是计算机科学中的基础但至关重要的概念,尤其在数据处理和算法设计中扮演着核心角色。本文将深入探讨标题中提到的几种基于比较的排序算法:选择排序、插入排序、归并排序、快速排序、堆排序、冒泡...
最快的排序算法 最快的内部排序法—桶排序法 (1),排序算法数据结构
在计算机科学领域中,排序算法是一种基本的算法,它可以将数据按照一定的顺序排列,以便更好地存储、检索和处理数据。排序算法的速度和效率对程序的性能有着至关重要的影响。 1.冒泡排序算法 冒泡排序算法是一种...
该程序包含7大排序算法: # sort.bubbleSort() #冒泡排序 # sort.shellSort() #希尔排序 # sort.insertionSort() #插入排序 # sort.Selectionsort1() #选择排序 # sort.heapSort() #堆排序 # sort.countSort() ...
根据给定文件的信息,本文将深入探讨C语言中的两种经典排序方法:插入排序法与冒泡排序法。这两种方法在实际编程中应用广泛,对于理解数据结构与算法的基础概念至关重要。 ### 一、冒泡排序法 #### 1.1 基本原理 ...
双向起泡排序法是一种在链表结构中实现的排序算法,尤其适用于双向链表。它借鉴了传统冒泡排序的基本思想,但在链表环境中进行了优化,以提高效率。本篇文章将详细探讨双向起泡排序法及其在带头结点的双向链表中的...
六种排序算法的排序系统 本篇文章主要讲解了六种排序算法的排序系统,包括插入排序、冒泡排序、选择排序、快速排序、堆排序和归并排序。该系统可以让用户选择六种排序算法中的任意一个,并输出结果。 插入排序 ...
在IT领域,排序算法是计算机科学中的基础但至关重要的部分,尤其在数据处理和数据分析中起着关键作用。本文将详细探讨标题所提及的几种排序算法:合并排序、插入排序、希尔排序、快速排序、冒泡排序以及桶排序,并...
在计算机科学中,排序算法是数据结构领域的重要组成部分,它涉及到如何有效地重新排列一组数据,使其按照特定的顺序排列。本资源提供了三种经典的排序算法的C语言实现:堆排序、直接插入排序和快速排序。 首先,让...
在计算机科学领域,排序算法是数据处理中至关重要的一部分,它涉及到如何有效地重新排列一组数据,使其按照特定的顺序排列。本资源提供了七大经典排序算法的实现程序,包括快速排序、冒泡排序、选择排序、归并排序、...
时间复杂度用于衡量排序算法的效率,通常以大O表示法来表示。文档中提到了几种不同排序算法的时间复杂度: - **O(n²)**:插入排序、冒泡排序和选择排序的时间复杂度均为O(n²),这意味着随着数据量的增加,这些...
排序算法是计算机科学中最基础和重要的算法之一,用于将一组数据按照特定的顺序进行排列。本文将对几种常见的内部排序算法和外部排序算法进行详细总结。 首先,排序的基本定义是:给定一个包含n个记录的序列,其...
在编程领域,排序算法是计算机科学中的重要组成部分,特别是在数据处理和算法效率分析上。本文将详细介绍C++中实现的希尔排序、快速排序、堆排序和归并排序这四种经典排序算法。 希尔排序,由Donald Shell于1959年...