package sort; public class DataWrap implements Comparable<DataWrap>{ int data; String flag; public DataWrap(int data,String flag){ this.data = data; this.flag = flag; } public String toString(){ return data + flag; } //根据data实例变量来决定两个dataWrap的大小 @Override public int compareTo(DataWrap dw) { return this.data > dw.data? 1 : (this.data == dw.data? 0 : -1); } }
直接插入排序
package sort; /** * 直接插入排序 * @author shkstart * 2013-11-27 */ public class InsertSort { public static void insertSort(DataWrap[] data){ System.out.println("开始排序"); int arrayLength = data.length; for(int i = 1;i < arrayLength;i++){ DataWrap temp = data[i]; if(data[i].compareTo(data[i-1]) < 0){ int j = i -1; for(;j >= 0 && data[j].compareTo(temp) > 0;j--){ data[j +1] = data[j]; } data[j + 1] = temp; } System.out.println(java.util.Arrays.toString(data)); } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "")}; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); insertSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
折半插入排序
package sort; /** * 折半插入排序 * @author shkstart * 2013-11-27 */ public class BinaryInsertSort { public static void binaryInsertSort(DataWrap[] data) { System.out.println("开始排序"); int arrayLength = data.length; for (int i = 1; i < arrayLength; i++) { DataWrap temp = data[i]; int low = 0; int high = i - 1; while (low <= high) { int mid = (low + high) / 2; if (temp.compareTo(data[mid]) > 0) { low = mid + 1; } else { high = mid - 1; } } for (int j = i; j > low; j--) { data[j] = data[j - 1]; } data[low] = temp; System.out.println(java.util.Arrays.toString(data)); } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "")}; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); binaryInsertSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
Shell排序
package sort; /** * Shell排序 * @author shkstart * 2013-11-27 */ public class ShellSort { public static void ShellSort(DataWrap[] data) { System.out.println("开始排序"); int arrayLength = data.length; int h = 1; while (h <= arrayLength / 3) { h = h * 3 + 1; } while (h > 0) { System.out.println("===h的值:" + h + "==="); for (int i = h; i < arrayLength; i++) { DataWrap temp = data[i]; if (data[i].compareTo(data[i - h]) < 0) { int j = i - h; for (; j >= 0 && data[j].compareTo(temp) > 0; j -= h) { data[j + h] = data[j]; } data[j + h] = temp; } System.out.println(java.util.Arrays.toString(data)); } h = (h - 1) / 3; } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "")}; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); ShellSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
直接选择排序
package sort; /** * 直接选择排序 * @author shkstart * 2013-11-27 */ public class SelectSort { public static void selectSort(DataWrap[] data) { System.out.println("开始排序"); int arrayLength = data.length; for (int i = 0; i < arrayLength - 1; i++) { for (int j = i + 1; j < arrayLength; j++) { if (data[i].compareTo(data[j]) > 0) { DataWrap temp = data[i]; data[i] = data[j]; data[j] = temp; } } System.out.println(java.util.Arrays.toString(data)); } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "") }; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); selectSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
直接选择排序-改进
package sort; /** * 直接选择排序-改进 * @author shkstart * 2013-11-27 */ public class SelectSort2 { public static void selectSort(DataWrap[] data) { System.out.println("开始排序"); int arrayLength = data.length; for (int i = 0; i < arrayLength - 1; i++) { int minIndex = i; for (int j = i + 1; j < arrayLength; j++) { if (data[minIndex].compareTo(data[j]) > 0) { minIndex = j; } } if(minIndex != i){ DataWrap temp = data[i]; data[i] = data[minIndex]; data[minIndex] = temp; } System.out.println(java.util.Arrays.toString(data)); } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "") }; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); selectSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
堆排序
package sort; /** * 堆排序 * @author shkstart * 2013-11-27 */ public class HeapSort { public static void heapSort(DataWrap[] data) { System.out.println("开始排序"); int arrayLength = data.length; // 循环建堆 for (int i = 0; i < arrayLength - 1; i++) { // 建堆 builMaxdHeap(data, arrayLength - 1 - i); // 交换堆顶和最后一个元素 swap(data, 0, arrayLength - 1 - i); System.out.println(java.util.Arrays.toString(data)); } } // 对data数组从0到lastIndex建大顶堆 private static void builMaxdHeap(DataWrap[] data, int lastIndex) { // 从lastIndex处节点(最后一个节点)的父节点开始 for (int i = (lastIndex - 1) / 2; i >= 0; i--) { // k保存当前正在判断的节点 int k = i; // 如果当前k节点的子节点存在 while (k * 2 + 1 <= lastIndex) { // k节点的左子节点的索引 int biggerIndex = 2 * k + 1; // 如果biggerIndex小于lastIndex,即biggerIndex +1 // 代表k节点的右子节点存在 if (biggerIndex < lastIndex) { // 如果右子节点的值较大 if (data[biggerIndex].compareTo(data[biggerIndex + 1]) < 0) { // biggerIndex总是记录较大子节点的索引 biggerIndex++; } } // 如果k节点的值小于其较大子节点的值 if (data[k].compareTo(data[biggerIndex]) < 0) { // 交换它们 swap(data, k, biggerIndex); // 将biggerIndex赋给k,开始while循环的下一次循环 // 重新保证k节点的值大于其左、右节点的值 k = biggerIndex; } else { break; } } } } // 交换data数组中i、j两个索引处的元素 private static void swap(DataWrap[] data, int i, int j) { DataWrap temp = data[i]; data[i] = data[j]; data[j] = temp; } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "")}; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); heapSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
冒泡排序
package sort; /** * 冒泡排序 * @author shkstart * 2013-11-27 */ public class BubbleSort { public static void bubbleSort(DataWrap[] data) { System.out.println("开始排序"); int arrayLength = data.length; for (int i = 0; i < arrayLength - 1; i++) { boolean flag = false; for (int j = 0; j < arrayLength - 1 - i; j++) { if (data[j].compareTo(data[j + 1]) > 0) { DataWrap temp = data[j + 1]; data[j + 1] = data[j]; data[j] = temp; flag = true; } } System.out.println(java.util.Arrays.toString(data)); if (!flag) break; } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "")}; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); bubbleSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
快速排序
package sort; /** * 快速排序 * @author shkstart * 2013-11-27 */ public class QuickSort { private static void swap(DataWrap[] data, int i, int j) { DataWrap temp = data[i]; data[i] = data[j]; data[j] = temp; } private static void subSort(DataWrap[] data, int start, int end) { if (start < end) { DataWrap base = data[start]; int i = start; int j = end + 1; while (true) { while (i < end && data[++i].compareTo(base) <= 0) ; while (j > start && data[--j].compareTo(base) >= 0) ; if (i < j) { swap(data, i, j); } else { break; } } swap(data, start, j); subSort(data, start, j - 1); subSort(data, j + 1, end); } } public static void quickSort(DataWrap[] data){ subSort(data,0,data.length-1); } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "") }; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); quickSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
归并排序
package sort; /** * 归并排序 * * @author shkstart * 2013-11-27 */ public class MergeSort { public static void mergeSort(DataWrap[] data) { // 归并排序 sort(data, 0, data.length - 1); } // 将索引从left到right范围的数组元素进行归并排序 private static void sort(DataWrap[] data, int left, int right) { if(left < right){ //找出中间索引 int center = (left + right)/2; sort(data,left,center); sort(data,center+1,right); //合并 merge(data,left,center,right); } } // 将两个数组进行归并,归并前两个数组已经有序,归并后依然有序 private static void merge(DataWrap[] data, int left, int center, int right) { DataWrap[] tempArr = new DataWrap[data.length]; int mid = center + 1; int third = left; int temp = left; while (left <= center && mid <= right) { if (data[left].compareTo(data[mid]) <= 0) { tempArr[third++] = data[left++]; } else { tempArr[third++] = data[mid++]; } } while (mid <= right) { tempArr[third++] = data[mid++]; } while (left <= center) { tempArr[third++] = data[left++]; } while (temp <= right) { data[temp] = tempArr[temp++]; } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""), new DataWrap(21, "*"), new DataWrap(23, ""), new DataWrap(-30, ""), new DataWrap(-49, ""), new DataWrap(21, ""), new DataWrap(30, "*"), new DataWrap(30, "") }; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); mergeSort(data); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
基数排序
package sort; import java.util.Arrays; /** * 基数排序 * * @author shkstart 2013-11-27 */ public class MultiKeyRadixSort { public static void radixSort(int[] data, int radix, int d) { System.out.println("开始排序:"); int arrayLength = data.length; int[] temp = new int[arrayLength]; int[] buckets = new int[radix]; for (int i = 0, rate = 1; i < d; i++) { // 重置count数组,开始统计第二个关键字 Arrays.fill(buckets, 0); // 当data数组的元素复制到temp数组中进行缓存 System.arraycopy(data, 0, temp, 0, arrayLength); for (int j = 0; j < arrayLength; j++) { int subKey = (temp[j] / rate) % radix; buckets[subKey]++; } for (int j = 1; j < radix; j++) { buckets[j] = buckets[j] + buckets[j - 1]; } for (int m = arrayLength - 1; m >= 0; m--) { int subKey = (temp[m] / rate) % radix; data[--buckets[subKey]] = temp[m]; } System.out.println("对" + rate + "位上子关键字排序:" + java.util.Arrays.toString(data)); rate *= radix; } } public static void main(String[] args) { int[] data = { 1100, 192, 221, 12, 13 }; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); radixSort(data, 10, 4); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
桶式排序
package sort; import java.util.Arrays; /** * 桶式排序 * * @author shkstart * 2013-11-27 */ public class BucketSort { public static void bucketSort(DataWrap[] data, int min, int max) { System.out.println("开始排序"); int arrayLength = data.length; DataWrap[] temp = new DataWrap[arrayLength]; int[] buckets = new int[max - min]; for (int i = 0; i < arrayLength; i++) { buckets[data[i].data - min]++; } System.out.println(Arrays.toString(buckets)); for (int i = 1; i < max - min; i++) { buckets[i] = buckets[i] + buckets[i - 1]; } System.out.println(Arrays.toString(buckets)); System.arraycopy(data, 0, temp, 0, arrayLength); for (int k = arrayLength - 1; k >= 0; k--) { data[--buckets[temp[k].data - min]] = temp[k]; } } public static void main(String[] args) { DataWrap[] data = { new DataWrap(9, ""), new DataWrap(5, ""), new DataWrap(-1, ""), new DataWrap(8, ""), new DataWrap(5, "*"), new DataWrap(7, ""), new DataWrap(3, ""), new DataWrap(-3, ""), new DataWrap(1, ""),new DataWrap(3, "*")}; System.out.println("排序之前:\n" + java.util.Arrays.toString(data)); bucketSort(data, -3, 10); System.out.println("排序之后:\n" + java.util.Arrays.toString(data)); } }
捐助开发者
在兴趣的驱动下,写一个免费
的东西,有欣喜,也还有汗水,希望你喜欢我的作品,同时也能支持一下。 当然,有钱捧个钱场(右上角的爱心标志,支持支付宝和PayPal捐助),没钱捧个人场,谢谢各位。
谢谢您的赞助,我会做的更好!
相关推荐
在本文中,我们将深入探讨如何使用Qt5框架和C++编程语言实现九大经典的排序算法。Qt5是一个跨平台的应用程序开发框架,它提供了丰富的库和工具,使得开发人员能够便捷地构建用户界面和应用程序逻辑。C++则是一种强大...
本资源提供了七大经典排序算法的实现程序,包括快速排序、冒泡排序、选择排序、归并排序、插入排序、希尔排序和堆排序。下面将逐一详细介绍这些排序算法及其原理。 1. 快速排序:由C.A.R. Hoare提出,是一种采用...
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
1. 冒泡排序:冒泡排序是一种简单的交换排序方法,通过不断比较相邻元素并交换位置,将较大的元素逐渐“冒泡”到数组的末尾。虽然效率较低(时间复杂度为O(n^2)),但实现起来相对直观。 2. 选择排序:选择排序每次...
合并排序是一种分治策略的排序算法,它将大问题分解成小问题来解决。首先将数组分为两个子数组,分别对它们进行排序,然后将两个有序的子数组合并为一个有序的大数组。该算法的时间复杂度为O(n log n),适合处理大...
堆排序分为建堆和调整堆两个阶段,首先将无序序列构造成一个大顶堆或小顶堆,然后将堆顶元素与末尾元素交换,调整剩下的元素为新的堆,如此反复进行,直到所有元素排序完毕。堆排序是一种不稳定的排序方法,但效率...
选择排序的时间复杂度始终为O(n^2),不适用于大数据量排序。 5. **堆排序**:利用堆这种数据结构实现排序,分为建堆和调整堆两步。C#中,可以使用System.Collections.Generic.PriorityQueue类辅助实现。堆排序在最...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
例如,冒泡排序和选择排序适合小规模数据,而快速排序和归并排序则适用于大规模数据。在实际应用中,应根据具体需求和数据特性选择合适的排序算法。学习和理解这些排序算法的原理及源码实现,对于提升编程能力具有...
在实际应用中,选择合适的排序算法能够极大地提高程序的效率和性能。 总结一下,这四种排序算法各有特色,适用场景不同。堆排序和快速排序是基于比较的排序,而基数排序和计数排序是非比较型的。理解并能熟练运用...
根据给定的信息,本文将详细介绍九种排序算法中的四种,并且提供C语言版本的实现代码。这四种排序算法包括:选择排序、直接插入排序、冒泡排序和希尔排序。 ### 1. 选择排序(Select Sort) #### 算法原理: 选择...
例如,直接插入排序和冒泡排序适合小规模数据,而快速排序和堆排序则适用于大规模数据。选择排序和希尔排序在某些特定条件下也能展现出较高的效率。在实际应用中,我们需要根据数据的特性、内存限制以及时间效率要求...
在计算机科学中,排序算法是数据处理的重要组成部分,尤其是在大数据处理和数据分析中。本文将深入探讨Java编程语言中实现的七种主要排序算法:直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序以及...
首先,将待排序数组构建成一个大顶堆或小顶堆,然后将堆顶元素与末尾元素交换,调整剩余元素为新的堆,重复此过程。C++实现时,可以使用标准库中的`<algorithm>`中的`make_heap`、`pop_heap`和`sort_heap`函数。堆...
堆排序先构建一个大顶堆(或小顶堆),然后将堆顶元素(最大或最小元素)与末尾元素交换,接着调整剩余元素成堆,如此反复,直到所有元素都有序。 3. **快速排序**:快速排序由C.A.R. Hoare提出,是目前最常用的...
堆排序先将数组构建成一个大顶堆,然后将堆顶元素(最大值)与末尾元素交换,再调整剩下的元素为堆,如此反复进行。堆排序的平均和最坏时间复杂度均为O(n log n)。 这些排序算法各有优缺点,适用于不同的场景。例如...
本资源包包含了九种经典的内部排序算法的源代码,涵盖了从基础到高效的多种方法,但遗憾的是未包含桶排序。以下是这些排序算法的详细介绍: 1. 冒泡排序(Bubble Sort): 冒泡排序是最简单的排序算法之一,通过...
它将待排序的序列构建为一个大顶堆或小顶堆,然后交换堆顶元素(最大或最小元素)与末尾元素,缩小排序范围,重复此过程,直到所有元素排序完毕。堆排序的时间复杂度为O(n log n),空间复杂度为O(1)。 2. **选择...
交换排序可以看作是一种广义的排序策略,其中冒泡排序和选择排序都可以归类于这一大类。其核心在于两两比较相邻元素,如果顺序错误则进行交换,直至整个序列有序。 ### 4. 希尔排序(Shell Sort) 希尔排序是插入...
尽管冒泡排序在概念上易于理解和实现,但由于其时间复杂度为O(n^2),对于大数据量的排序效率较低,不适用于大规模数据处理场景。然而,可以通过以下方式对其进行优化: 1. **添加标志位**:在每轮遍历中添加一个...