稳定性比较
稳定:插入排序、冒泡排序、二叉树排序、二路归并排序
不稳定:选择排序、希尔排序、快速排序、堆排序
时间复杂性比较
插入排序、冒泡排序、选择排序为O(n^2)
其它为O(nlog2n)
1.
/*
* 题目：对10个数进行排序
*/
// 冒泡排序
// 已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。
// 再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比较a[3]与a[4]，以此类推，最后比较a[n-1]与a[n]的值。
// 这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮，则a[n-1]的值一定是a[1]~a[n-1]中最大的。
// 再对a[1]~a[n-2]以相同方法处理一轮，以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。降序排列与升序排列相类似，
// 若a[1]小于a[2]则交换两者的值，否则不变，后面以此类推。
// 总的来讲，每一轮排序后最大（或最小）的数将移动到数据序列的最后，理论上总共要进行n(n-1）/2次交换。
public static void print32(int[] nums) {
System.out.println("冒泡排序");
System.out.println("原数组" + Arrays.toString(nums));
long start = System.currentTimeMillis();
int len = nums.length;
int count = 0;
int count2 = 0;
int count3 = 0;
for (int i = len - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
count2++;
if (nums[j] > nums[j + 1]) {
count3++;
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
System.out.println("第" + (++count) + "次" + Arrays.toString(nums));
}
long end = System.currentTimeMillis();
System.out.println("用时" + (end - start) + "毫秒,循环" + count2 + "次,交换" + count3 + "次");
}
/*
* 题目：对10个数进行排序
*/
// 选择排序
// 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最前（或最后），直到全部待排序的数据元素排完。
// 在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，
// 使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
public static void print33(int[] nums) {
System.out.println("选择排序");
System.out.println("原数组" + Arrays.toString(nums));
long start = System.currentTimeMillis();
int len = nums.length;
int count = 0;
int count2 = 0;
int count3 = 0;
int count4 = 0;
for (int i = 0; i < len; i++) {
int index = i;
for (int j = i + 1; j < len; j++) {
count2++;
if (nums[index] > nums[j]) {
count3++;
index = j;
}
}
if (index != i) {
count4++;
int temp = nums[i];
nums[i] = nums[index];
nums[index] = temp;
}
System.out.println("第" + (++count) + "次" + Arrays.toString(nums));
}
long end = System.currentTimeMillis();
System.out.println("用时" + (end - start) + "毫秒,循环" + count2 + "次,交换下标" + count3 + "次,交换" + count4 + "次");
}
/*
* 题目：对10个数进行排序
*/
// 插入排序
// ⒈ 从第一个元素开始，该元素可以认为已经被排序
// ⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
// ⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
// ⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
// ⒌ 将新元素插入到下一位置中
// ⒍ 重复步骤2
public static void print34(int[] nums) {
System.out.println("插入排序");
System.out.println("原数组" + Arrays.toString(nums));
long start = System.currentTimeMillis();
int len = nums.length;
int count = 0;
int count2 = 0;
int count3 = 0;
for (int i = 1; i < len; i++) {
int index = i;
int data = nums[index];
count2++;
while (index > 0 && (nums[index - 1] > data)) {
count2++;
count3++;
nums[index] = nums[index - 1];
index--;
}
nums[index] = data;
System.out.println("第" + (++count) + "次" + Arrays.toString(nums));
}
long end = System.currentTimeMillis();
System.out.println("用时" + (end - start) + "毫秒,循环" + count2 + "次,交换" + count3 + "次");
}
/*
* 题目：对10个数进行排序(选择排序)
*/
public static void print39(int[] nums) {
System.out.print("数组" + Arrays.toString(nums));
long start = System.currentTimeMillis();
int len = nums.length;
int count = 0;
int count2 = 0;
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
count++;
if (nums[i] > nums[j]) {
count2++;
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}
long end = System.currentTimeMillis();
System.out.println("排序后为" + Arrays.toString(nums) + ",用时" + (end - start) + "毫秒,循环" + count + "次,交换" + count2 + "次");
}
public static void main(String[] args) {
int[] nums = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
int[] nums2 = { 10, 1, 9, 2, 8, 3, 7, 4, 6, 5 };
T2.print32(nums.clone());
System.out.println("----------------------------------------");
T2.print33(nums.clone());
System.out.println("----------------------------------------");
T2.print34(nums.clone());
System.out.println("----------------------------------------");
System.out.println("----------------------------------------");
T2.print32(nums2.clone());
System.out.println("----------------------------------------");
T2.print33(nums2.clone());
System.out.println("----------------------------------------");
T2.print34(nums2.clone());
}
输出：
冒泡排序 原数组[10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 第1次[9, 8, 7, 6, 5, 4, 3, 2, 1, 10] 第2次[8, 7, 6, 5, 4, 3, 2, 1, 9, 10] 第3次[7, 6, 5, 4, 3, 2, 1, 8, 9, 10] 第4次[6, 5, 4, 3, 2, 1, 7, 8, 9, 10] 第5次[5, 4, 3, 2, 1, 6, 7, 8, 9, 10] 第6次[4, 3, 2, 1, 5, 6, 7, 8, 9, 10] 第7次[3, 2, 1, 4, 5, 6, 7, 8, 9, 10] 第8次[2, 1, 3, 4, 5, 6, 7, 8, 9, 10] 第9次[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 用时0毫秒,循环45次,交换45次 ---------------------------------------- 选择排序 原数组[10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 第1次[1, 9, 8, 7, 6, 5, 4, 3, 2, 10] 第2次[1, 2, 8, 7, 6, 5, 4, 3, 9, 10] 第3次[1, 2, 3, 7, 6, 5, 4, 8, 9, 10] 第4次[1, 2, 3, 4, 6, 5, 7, 8, 9, 10] 第5次[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 第6次[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 第7次[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 第8次[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 第9次[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 第10次[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 用时0毫秒,循环45次,交换下标25次,交换5次 ---------------------------------------- 插入排序 原数组[10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 第1次[9, 10, 8, 7, 6, 5, 4, 3, 2, 1] 第2次[8, 9, 10, 7, 6, 5, 4, 3, 2, 1] 第3次[7, 8, 9, 10, 6, 5, 4, 3, 2, 1] 第4次[6, 7, 8, 9, 10, 5, 4, 3, 2, 1] 第5次[5, 6, 7, 8, 9, 10, 4, 3, 2, 1] 第6次[4, 5, 6, 7, 8, 9, 10, 3, 2, 1] 第7次[3, 4, 5, 6, 7, 8, 9, 10, 2, 1] 第8次[2, 3, 4, 5, 6, 7, 8, 9, 10, 1] 第9次[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 用时0毫秒,循环54次,交换45次 ---------------------------------------- ---------------------------------------- 冒泡排序 原数组[10, 1, 9, 2, 8, 3, 7, 4, 6, 5] 第1次[1, 9, 2, 8, 3, 7, 4, 6, 5, 10] 第2次[1, 2, 8, 3, 7, 4, 6, 5, 9, 10] 第3次[1, 2, 3, 7, 4, 6, 5, 8, 9, 10] 第4次[1, 2, 3, 4, 6, 5, 7, 8, 9, 10] 第5次[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 第6次[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 第7次[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 第8次[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 第9次[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 用时0毫秒,循环45次,交换25次 ---------------------------------------- 选择排序 原数组[10, 1, 9, 2, 8, 3, 7, 4, 6, 5] 第1次[1, 10, 9, 2, 8, 3, 7, 4, 6, 5] 第2次[1, 2, 9, 10, 8, 3, 7, 4, 6, 5] 第3次[1, 2, 3, 10, 8, 9, 7, 4, 6, 5] 第4次[1, 2, 3, 4, 8, 9, 7, 10, 6, 5] 第5次[1, 2, 3, 4, 5, 9, 7, 10, 6, 8] 第6次[1, 2, 3, 4, 5, 6, 7, 10, 9, 8] 第7次[1, 2, 3, 4, 5, 6, 7, 10, 9, 8] 第8次[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 第9次[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 第10次[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 用时1毫秒,循环45次,交换下标15次,交换7次 ---------------------------------------- 插入排序 原数组[10, 1, 9, 2, 8, 3, 7, 4, 6, 5] 第1次[1, 10, 9, 2, 8, 3, 7, 4, 6, 5] 第2次[1, 9, 10, 2, 8, 3, 7, 4, 6, 5] 第3次[1, 2, 9, 10, 8, 3, 7, 4, 6, 5] 第4次[1, 2, 8, 9, 10, 3, 7, 4, 6, 5] 第5次[1, 2, 3, 8, 9, 10, 7, 4, 6, 5] 第6次[1, 2, 3, 7, 8, 9, 10, 4, 6, 5] 第7次[1, 2, 3, 4, 7, 8, 9, 10, 6, 5] 第8次[1, 2, 3, 4, 6, 7, 8, 9, 10, 5] 第9次[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 用时0毫秒,循环34次,交换25次
相关推荐
在本系统中，我们主要实现了五种常用的排序算法：冒泡排序法、快速排序法、直接插入排序法、折半插入排序法和树形选择排序法。这些算法都是在计算机科学中最基本和最重要的排序算法，广泛应用于各种数据处理和分析...
常见的经典排序算法有希尔排序、二分插入法、直接插入法、带哨兵的直接排序法、冒泡排序、选择排序、快速排序、堆排序等。 一、希尔排序（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年...