常见内部排序算法
包括选择
排序算法,交换排序算法,插入排序算法,基数算法,桶式算法还有归并算法。
其中选择排序算法又包括:
简单选择排序算法与
堆排序。
选择算法,顾名思义,就是从中选择需要的,然后再与目标地址进行交换。
简单选择排序算法:
package test.aglorith;
public class SelectSort {
//从小到大
public void sort(int[] data) {
int data_len=data.length;
for (int i = 0; i < data_len; i++) {
int big=0;
for (int j=1;j<data_len-i;j++) {
if (data[big]<data[j]) {
big=j;
}
}
int point=data_len-1-i;
if (big!=point) {
int temp=data[point];
data[point]=data[big];
data[big]=temp;
}
print(data);
System.out.println("");
}
}
public static void print(int[] data) {
for(int d:data){
System.out.print(d+",");
}
}
public static void main(String[] args) {
int[] data=new int[]{1,10,2,5,3,6,9};
System.out.println("排序之前!");
print(data);
System.out.println("");
System.out.println("开始排序!");
new SelectSort().sort(data);
}
}
堆排序:包括大顶堆,小顶堆。根据不同需求把根节点与最后一个元素进行交换,每次都循环一个
建堆-交换的过程。下面是大顶堆例子:
package test.aglorith;
public class HeapSort {
//排序入口
public void sort(int[] data) {
int lastIndex=data.length-1;
for (int i = 0; i < data.length; i++) {
buildHeap(data, lastIndex-i);
swap(data, 0,lastIndex-i);
print(data);
System.out.println(i);
}
}
//建堆过程
public static void buildHeap(int[] data,int lastIndex) {
for(int i=((lastIndex-1)/2);i>=0;i--){
int k=i;
while(2*k+1<lastIndex){
int biggerIndex=2*k+1;
//判断是否有右子节点
if (biggerIndex<lastIndex) {
//选择左右子节点中相对较大的
if (data[biggerIndex]<data[biggerIndex+1]) {
biggerIndex++;
}
}
if (data[k]<data[biggerIndex]) {
swap(data, k, biggerIndex);
k=biggerIndex;//need?有根没有相差不多
}else {
break;
}
}
}
}
//交换目标
public static void swap(int[] data,int i,int j) {
int temp=data[i];
data[i]=data[j];
data[j]=temp;
}
//打印
public static void print(int[] data) {
for(int d:data){
System.out.print(d+",");
}
}
public static void main(String[] args) {
int[] data=new int[]{1,10,2,5,3,6,9,19,15};
System.out.println("排序之前!");
print(data);
System.out.println("");
System.out.println("开始排序!");
long pre=System.currentTimeMillis();
for (int i = 0; i < 30000; i++) {
new HeapSort().sort(data);
}
long end=System.currentTimeMillis();
System.out.println((end-pre)/300);
}
}
分享到:
相关推荐
本文将深入探讨“C语言数据结构内部排序算法及比较”这一主题,结合个人课程作业的经验,对一些核心概念进行阐述,并对常见的内部排序算法进行比较。 首先,数据结构是组织和管理数据的方式,它包括数组、链表、树...
常见的内部排序算法包括起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序等。这些算法各有优缺点,在不同场景下具有不同的适用性。因此,深入研究和比较这些排序算法对于提高数据处理效率具有重要...
常见的内部排序算法包括但不限于: 1. **直接插入排序**:逐个遍历列表中的每个元素,将其插入到已排序序列的正确位置。适用于小规模数据集。 2. **冒泡排序**:重复遍历待排序序列,每次遍历时比较相邻两个元素,...
本篇文章将深入探讨10种常见的内部排序算法,包括它们的基本思想、比较次数和移动次数的计算,以便更直观地理解不同算法的效率。 1. **直接插入排序**: 直接插入排序是一种简单的排序算法,它通过比较新元素与已...
本文将对几种常见的内部排序算法和外部排序算法进行详细总结。 首先,排序的基本定义是:给定一个包含n个记录的序列,其关键字序列分别为K1, K2, ..., Kn,如果存在一个排列p1, p2, p3, ..., pn,使得关键字满足非...
本项目针对内部排序算法进行了性能分析,通过设计一个测试程序,对比了几种常见内部排序算法的关键字比较次数和移动次数,以帮助我们更直观地理解不同算法的效率差异。以下是关于内部排序算法的一些关键知识点: 1....
本报告主要关注了六种常见的内部排序算法:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序和堆排序,并通过实验比较它们在不同数据状态下的效率。 **一、算法原理** 1. **起泡排序**:通过不断交换...
常见的内部排序算法包括冒泡排序、选择排序、插入排序、堆排序、快速排序和希尔排序等。这些算法各有特点,适用于不同场景。 - **冒泡排序**:通过重复遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把...
根据给定的文章摘要和部分内容,本文旨在探讨内部排序算法,并对常见的几种内部排序方法进行比较与选择,以帮助读者理解不同排序算法的特点及其适用场景。接下来,我们将详细展开这一主题。 ### 排序的基本概念 ##...
内部排序算法是计算机科学基础课程——数据结构与算法中的核心内容之一。通过学习不同的内部排序算法,可以深刻理解算法的设计思想及其实现方法,同时也能为解决实际问题提供多种选择方案。 ### 常见的内部排序算法...
本文将深入探讨七种常见的内部排序算法:直接插入排序、折半插入排序、冒泡排序、简单选择排序、希尔排序、快速排序以及堆排序。通过对这些算法的比较次数和移动次数的分析,我们可以更好地理解它们的效率和适用场景...
广东工业大学的数据结构实验报告重点关注了几种常见的内部排序算法,包括直接插入排序、选择排序和快速排序。这些算法在不同的场景下具有不同的性能特征。 **直接插入排序**是一种简单直观的排序方法,适用于小规模...
本篇文章将深入探讨六种常见的内部排序算法:希尔排序、直接选择排序、快速排序、直接插入排序、堆排序以及冒泡排序。 希尔排序是一种基于插入排序的算法,由希尔在1959年提出。它通过将待排序数组按某个增量分组,...
下面我们将深入分析几种常见的内部排序算法:冒泡排序、选择排序、快速排序、插入排序以及希尔排序,并着重讨论它们在比较次数和移动次数上的表现。 ### 冒泡排序 冒泡排序是一种简单的排序算法,它重复地遍历待...
在本篇文章中,我们将深入探讨几种常见的内部排序算法,包括它们的原理、时间复杂度和空间复杂度,并通过代码实现来展示这些算法的运作过程。 1. 直接插入排序: 直接插入排序是一种简单的排序算法,它将数据分为已...
本资源包含快速排序、希尔排序、冒泡排序、插入排序等六种常见的内部排序算法的性能分析,通过源代码和相关文档,我们可以深入理解这些算法的工作原理以及它们在不同情况下的性能表现。 1. **快速排序**:由C.A.R. ...
以上是常见的基于比较的内部排序算法,每种都有其适用场景和优缺点。在实际应用中,选择合适的排序算法要考虑数据规模、数据特性以及时间与空间复杂度的需求。例如,对于大数据量且部分有序的数组,快速排序通常优于...
描述中提到,该设计已经通过了C语言的验证并能顺利运行,这意味着学生可能实现了如快速排序、归并排序、堆排序、插入排序、选择排序、冒泡排序、希尔排序等常见内部排序算法。每种算法都有其独特性,适用于不同的...
本文将详细探讨一款基于C++开发的内部排序图形化界面,该界面采用Microsoft Foundation Classes (MFC)库构建,实现了包括冒泡法、快速排序在内的六种常见排序算法,并提供了实时查看排序过程的功能,为学习和理解...