排序可以分为两大类：
内排序和
外排序
引用
在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序。
内排序有可以分为以下几类：
(1)、插入排序：直接插入排序、二分法插入排序、希尔排序。
(2)、选择排序：简单选择排序、堆排序。
(3)、交换排序：冒泡排序、快速排序。
(4)、归并排序
(5)、基数排序
/**
* 直接插入排序：
* 先将array中的第一位作为一个有序数列，然后取第二位放入T中，将第二位留出，
* 然后与第一位比较，如果第一位大的话，将第一位的元素放入留出的第二位中，由于i自减，第一位就放入T中的元素。
* 然后一次将第二位后的元素取出放入T中，逐个与前面有序的序列中的每个元素比较，通过交换，可以得到最终结果。
* @author xiaodai
*
*/
public class InsertionSort {
public static void main(String[] args) {
int[] array=new int[]{2,13,1,6,26,11,17};
/*for (int i = 1; i < array.length; i++) {
int t=array[i];
while(i > 0 && t < array[i-1]){
array[i]=array[i-1];
i--;
}
array[i]=t;
}*/
for (int i = 1; i < array.length; i++) {
int temp=array[i];
int j;
for (j = i-1; j >= 0; j--) {
if(temp < array[j]){
array[j+1]=array[j];
}else{
break;
}
}
array[j+1]=temp;
}
for (int i : array) {
System.out.print(i+" ");
}
}
}
/**
* 二分法排序:
* 在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们
* 中间的那个元素比，如果小，则对前半再进行折半，否则对后半
* 进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间
* 的所有元素后移，再把第i个元素放在目标位置上。
* @author xiaodai
*
*/
public class DichotomySort {
public static void main(String[] args) {
int[] array=new int[]{2,13,1,6,26,11,17};
for (int i = 0; i < array.length; i++) {
int start=0;
int end=i-1;
int mid=0;
int temp=array[i];
while(end>=start){
mid=(start+end)/2;
if(temp > array[mid]){
end=mid-1;
}else{
start=mid+1;
}
}
for (int j = i-1; j > end; j--) {
array[j+1]=array[j];
}
array[end+1]=temp;
}
for (int i : array) {
System.out.print(i+" ");
}
}
}
/**
* 希尔排序：
* 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。
* 所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；
* 然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，
* 即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
* @author xiaodai
*
*/
public class ShellSort {
public static void main(String[] args) {
int[] array=new int[]{2,13,1,6,26,11,17};
int group=array.length;
while(true){
group=group/2;
for (int i = 0; i < group; i++) {
for (int j = i+group; j < array.length; j=j+group) {
int temp=array[j];
int k;
for (k = j-group; k >= 0 && temp < array[k]; k=k-group) {
array[k+group]=array[k];
}
array[k+group]=temp;
}
}
if(group == 1){
break;
}
}
for (int i : array) {
System.out.print(i+" ");
}
}
}
/**
* 选择排序：
* 选择排序是假定第一个为最大，将第一个的下标赋给max，所以外层循环需要array.length-1次，
* 内层循环从外层循环选取的第一个元素后一位进行比较，选取第一个元素后面最大元素的下标，
* 使其与外层循环所选元素的下标进行交换，
* 最后在外层循环通过下标进行数值交换。
* @author xiaodai
*
*/
public class Selectionsort {
public static void main(String[] args) {
int[] array=new int[]{2,13,1,6,26,11,17};
for (int i = 0; i < array.length-1; i++) {
int max=i;
for (int j = i+1; j < array.length; j++) {
if(array[max]<array[j]){
max=j;
}
}
if(max!=i){
int temp=array[i];
array[i]=array[max];
array[max]=temp;
}
}
for (int i : array) {
System.out.print(i+" ");
}
}
}
/**
* 堆排序：初始时把要排序的数的序列看作是一棵顺序存储的二叉树，
* 调整它们的存储序，使之成为一个 堆，这时堆的根节点的数最大。
* 然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。
* 依此类推，直到只有两个节点的堆，并对 它们作交换，最后得到有n个节点的有序序列。
* 从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。
* 所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。
* @author xiaodai
*
*/
public class HeapSort {
public static void main(String[] args) {
int[] array=new int[]{2,13,1,6,26,11,17};
int arrayLength=array.length;
for (int i = 0; i < array.length-1; i++) {
buildMaxHeap(array, arrayLength-1-i);
swap(array, 0, arrayLength-1-i);
}
for (int i : array) {
System.out.print(i+" ");
}
}
public static void buildMaxHeap(int[] data, int 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]<data[biggerIndex+1]){
//biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
//如果k节点的值小于其较大的子节点的值
if(data[k]<data[biggerIndex]){
//交换他们
swap(data,k,biggerIndex);
//将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
k=biggerIndex;
}else{
break;
}
}
}
}
public static void swap(int[] data, int i, int j){
int temp=data[i];
data[i]=data[j];
data[j]=temp;
}
}
/**
* 冒泡排序：
* 进行冒泡排序需要从数组的开始元素开始，依次两两比较，这就需要比较length-1次（只有0~length-2需要比较，
* length-1不需要比较）。所以外层循环需要array.length-1次。
* 外层循环进行每次比较都会排除一个最大或者最小值，所以内层循环只需要比较j < array.length-1-i次。
* 在进行比较的时候，两两交换（次序可以有小到大，也可以由大到小）。
* @author xiaodai
*
*/
public class BubbleSort {
public static void main(String[] args) {
int[] array=new int[]{2,13,1,6,26,11,17};
for (int i = 0; i < array.length-1; i++) {
for (int j = 0; j < array.length-1-i; j++) {
if(array[j]>array[j+1]){
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
for (int i : array) {
System.out.print(i+" ");
}
}
}
/**
* 快速排序：选择一个基准元素,通常选择第一个元素或者最后一个元素,
* 通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,
* 此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
* @author xiaodai
*
*/
public class QuickSort {
public static void main(String[] args) {
int[] array=new int[]{2,13,1,6,26,11,17};
qs(array, 0, array.length-1);
for (int i : array) {
System.out.print(i+" ");
}
}
public static void qs(int[] data, int left, int right){
if(left < right){
int key = data[left];
int low = left;
int high = right;
while(low < high){
while(low < high && data[high] > key){
high--;
}
data[low] = data[high];
while(low < high && data[low] < key){
low++;
}
data[high] = data[low];
}
data[low] = key;
qs(data,left,low-1);
qs(data,low+1,right);
}
}
}
/**
* 归并排序：
* 将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。
* 然后再把有序子序列合并为整体有序序列。
* @author xiaodai
*
*/
public class MergeSort {
public static void main(String[] args) {
int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
mergeSort(a,0,a.length-1);
System.out.println();
System.out.println("排序之后：");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
}
private static void mergeSort(int[] a, int left, int right) {
if(left<right){
int middle = (left+right)/2;
//对左边进行递归
mergeSort(a, left, middle);
//对右边进行递归
mergeSort(a, middle+1, right);
//合并
merge(a,left,middle,right);
}
}
private static void merge(int[] a, int left, int middle, int right) {
int[] tmpArr = new int[a.length];
int mid = middle+1; //右边的起始位置
int tmp = left;
int third = left;
while(left<=middle && mid<=right){
//从两个数组中选取较小的数放入中间数组
if(a[left]<=a[mid]){
tmpArr[third++] = a[left++];
}else{
tmpArr[third++] = a[mid++];
}
}
//将剩余的部分放入中间数组
while(left<=middle){
tmpArr[third++] = a[left++];
}
while(mid<=right){
tmpArr[third++] = a[mid++];
}
//将中间数组复制回原数组
while(tmp<=right){
a[tmp] = tmpArr[tmp++];
}
}
}
/**
* 基数排序：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
* 然后，从最低位开始，依次进行一次排序。
* 这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
* @author xiaodai
*
*/
public class RadixSort {
public static void main(String[] args) {
int[] a={49,38,65,97,176,213,227,49,78,34,12,164,11,18,1};
//基数排序
sort(a);
System.out.println("排序之后：");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
}
private static void sort(int[] array) {
//找到最大数，确定要排序几趟
int max = 0;
for (int i = 0; i < array.length; i++) {
if(max<array[i]){
max = array[i];
}
}
//判断位数
int times = 0;
while(max>0){
max = max/10;
times++;
}
//建立十个队列
List<ArrayList> queue = new ArrayList<ArrayList>();
for (int i = 0; i < 10; i++) {
ArrayList queue1 = new ArrayList();
queue.add(queue1);
}
//进行times次分配和收集
for (int i = 0; i < times; i++) {
//分配
for (int j = 0; j < array.length; j++) {
int x = array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
ArrayList queue2 = queue.get(x);
queue2.add(array[j]);
queue.set(x,queue2);
}
//收集
int count = 0;
for (int j = 0; j < 10; j++) {
while(queue.get(j).size()>0){
ArrayList<Integer> queue3 = queue.get(j);
array[count] = queue3.get(0);
queue3.remove(0);
count++;
}
}
}
}
}
分享到：
相关推荐
这个名为"Java常见排序算法源码集.rar"的压缩文件显然包含了多种常用的排序算法的Java实现，对于初学者来说，这是一个非常宝贵的资源，可以深入理解各种算法的工作原理。 首先，我们来逐一探讨这些常见的排序算法：...
### Java 实现数据结构常见排序算法及详解 #### 排序算法概述 排序算法是计算机科学中的基础概念之一，主要用于将一系列数据按照特定规则进行排列。根据数据处理方式的不同，排序算法大致分为两大类：比较排序与非...
Java常见排序算法主要包括插入排序、冒泡排序、选择排序和希尔排序等。下面将分别详细介绍这几种排序算法的原理、特点和在Java中的实现。 1. 插入排序（Insertion Sort） 插入排序的原理是通过构建有序序列，对于未...
以上就是关于Java中常见排序算法（冒泡排序、选择排序、快速排序）的实现以及二叉树基本概念的介绍。这些算法和数据结构是编程学习中的重要组成部分，理解和熟练掌握它们对于解决实际问题大有裨益。通过不断的实践和...
Java中常见的排序算法 1.直接插入排序 2.希尔排序 3.选择排序 4.冒泡排序 5.归并排序 6.快速排序 7.堆排序 8.计数排序 9.桶排序 10.基数排序 包含这十种算法的讲解以及动态图解（ppt）和java实现
本压缩包"常见的七大排序算法Java实现.zip"包含了七种经典的排序算法在Java语言中的实现。尽管文件列表中并未明确列出每种排序算法的名称，但根据常规，这七大排序算法可能包括冒泡排序、插入排序、选择排序、快速...
`Algorithm.java`文件可能包含了这些排序算法的Java实现代码，而`常见排序算法的实现与性能比较.doc`文档则可能详细比较了这些算法的性能和适用场景。`readme.txt`文件可能是对整个项目的简要说明，包括如何运行和...
它通过将待排序的序列按照一定的增量分组，对每组使用直接插入排序算法排序，然后逐渐减少增量，直至增量为1，整个序列基本有序，最后再进行一次直接插入排序。希尔排序的时间复杂度在最坏的情况下为O(n^2)，但在...
本篇文章将详细探讨Java中常见的八种排序算法，每一种都有其独特的特性和适用场景。 1. **冒泡排序(Bubble Sort)** 冒泡排序是最基础的排序算法之一，通过不断交换相邻的逆序元素来逐步完成排序。它的时间复杂度为...
Java实现的常见排序算法 冒泡 选择 插叙 希尔
Java 排序算法概述 Java 排序算法是指在 Java 编程语言中使用的各种排序方法，旨在对数据进行有序排列。常见的排序算法有插入排序、交换排序、选择排序、归并排序、分配排序等。 插入排序是最基本的一种排序算法，...
常见排序算法的实现与性能比较JAVA 问题描述：实现合并排序，插入排序，希尔排序，快速排序，冒泡排序，桶排序算法 实验要求： A． 在随机产生的空间大小分别为 N = 10， 1000，10000，100000 的排序样本（取值为[0...
以上就是Java中几种常见排序算法的概述。在实际开发中，我们需要根据数据特性和性能要求选择合适的排序算法。例如，对于大数据量，快速排序和堆排序通常是更好的选择，而对于小规模或部分有序的数据，插入排序或冒泡...
以上就是Java中常见的几种排序算法，每种都有其适用场景和优缺点。实际编程中，我们会根据数据特性、性能需求和资源限制选择合适的排序算法。在实际的Java项目中，这些算法可以通过类、方法等方式实现，并在HTML文件...
本资源包含的是Java实现的各种常见排序算法的代码示例，每个算法都有详细的注释，方便初学者理解和学习。 1. **冒泡排序**：这是一种基础的排序算法，通过不断交换相邻的逆序元素来逐渐把较大的元素推向数组的后部...