java常用排序算法 java各种排序算法精编
【导读预览】此篇优秀范文“java常用排序算法 java各种排序算法精编”由阿拉题库网友为您整理分享，以供您参考学习之用，希望此篇资料对您有所帮助，喜欢就复制下载支持吧！
java常用排序算法 java各种排序算法篇1
一个排序算法是稳定的，就是当有两个相等记录的关键字r和s，且在原本的列表中r出现在s之前，在排序过的列表中r也将会是在s之前。
常见的有插入（插入排序/希尔排序）、交换（冒泡排序/快速排序）、选择（选择排序）、合并（归并排序）等。
插入排序（insertion sort），它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到o(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：从第一个元素开始，该元素可以认为已经被排序。取出下一个元素，在已经排序的元素序列中从后向前扫描。如果该元素（已排序）大于新元素，将该元素移到下一位置。重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。将新元素插入到该位置后。重复步骤2~5。
复制代码 代码如下:
public static void ionsort(int[] data) {
for (int index = 1; index < ; index++) {
int key = data[index];
int position = index;
// shift larger values to the right
while (position > 0 && data[position - 1] > key) {
data[position] = data[position - 1];
position--;
}
data[position] = key;
}
}
希尔排序(shell sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因dl．shell于1959年提出而得名。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率。但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位。
复制代码 代码如下:
staticvoid shellsort(lista) {
int h = 1;
while (h < ()/3) h = h*3 + 1; //: 1, 4, 13, 40, 121, ...
for (; h >= 1; h /= 3)
for (int i = h; i < (); i++)
for (int j = i; j >= h && (j).compareto((j-h)) < 0; j-=h)
(a, j, j-h);
}
冒泡排序（bubble sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序算法的运作如下：
比较相邻的元素，如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
复制代码 代码如下:
public static void bubblesort(int[] data) {
int temp = 0;
for (int i = - 1; i > 0; --i) {
boolean issort = false;
for (int j = 0; j < i; ++j) {
if (data[j + 1] < data[j]) {
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
issort = true;
}
}
// 如果一次内循环中发生了交换，那么继续比较；如果一次内循环中没发生任何交换，则认为已经排序好了。
if (!issort)
break;
}
}
快速排序（quicksort）是对冒泡排序的一种改进。由c. a. r. hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序使用分治法（spanide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
步骤为：
从数列中挑出一个元素，称为 "基准"（pivot）。重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
复制代码 代码如下:
/*
* more efficient implements for quicksort.
* use left, center and right median value (@see #median()) for the pivot, and
* the more efficient inner loop for the core of the algorithm.
*/
public class quicksort {
public static final int cutoff = 11;
/**
* quick sort algorithm.
*
* @param arr an array of comparable items.
*/
public staticvoid quicksort(t[] arr) {
quicksort(arr, 0, - 1);
}
/**
* get the median of the left, center and right.
* order these and hide the pivot by put it the end of of the array.
*
* @param arr an array of comparable items.
* @param left the most-left index of the subarray.
* @param right the most-right index of the subarray.
* @return t
*/
public statict median(t[] arr, int left, int right) {
int center = (left + right) / 2;
if (arr[left].compareto(arr[center]) > 0)
swapref(arr, left, center);
if (arr[left].compareto(arr[right]) > 0)
swapref(arr, left, right);
if (arr[center].compareto(arr[right]) > 0)
swapref(arr, center, right);
swapref(arr, center, right - 1);
return arr[right - 1];
}
/**
* internal method to sort the array with quick sort algorithm.
*
* @param arr an array of comparable items.
* @param left the left-most index of the subarray.
* @param right the right-most index of the subarray.
*/
private staticvoid quicksort(t[] arr, int left, int right) {
if (left + cutoff <= right) {
// find the pivot
t pivot = median(arr, left, right);
// start partitioning
int i = left, j = right - 1;
for (;;) {
while (arr[++i].compareto(pivot) < 0);
while (arr[--j].compareto(pivot) > 0);
if (i < j)
swapref(arr, i, j);
else
break;
}
// swap the pivot reference back to the small collection.
swapref(arr, i, right - 1);
quicksort(arr, left, i - 1); // sort the small collection.
quicksort(arr, i + 1, right); // sort the large collection.
} else {
// if the total number is less than cutoff we use ion sort
// instead (cause it much more efficient).
ionsort(arr, left, right);
}
}
/**
* method to swap references in an array.
*
* @param arr an array of objects.
* @param idx1 the index of the first element.
* @param idx2 the index of the second element.
*/
public staticvoid swapref(t[] arr, int idx1, int idx2) {
t tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
/**
* method to sort an subarray from start to end with ion sort
* algorithm.
*
* @param arr an array of comparable items.
* @param start the begining position.
* @param end the end position.
*/
public staticvoid ionsort(t[] arr, int start, int end) {
int i;
for (int j = start + 1; j <= end; j++) {
t tmp = arr[j];
for (i = j; i > start && eto(arr[i - 1]) < 0; i--) {
arr[i] = arr[i - 1];
}
arr[i] = tmp;
}
}
private static void printarray(integer[] c) {
for (int i = 0; i < ; i++)
(c[i] + ",");
ln();
}
public static void main(string[] args) {
integer[] data = {10, 4, 9, 23, 1, 45, 27, 5, 2};
ln("bubblesort...");
printarray(data);
quicksort(data);
printarray(data);
}
}
选择排序(selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
因为每一趟确定元素的过程中都会有一个选择最小值的子流程，所以人们形象地称之为选择排序。
举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
复制代码 代码如下:
public static void selectsort(int[] data) {
int minindex = 0;
int temp = 0;
for (int i = 0; i < ; i++) {
minindex = i; // 无序区的最小数据数组下标
for (int j = i + 1; j < ; j++) { // 在无序区中找到最小数据并保存其数组下标
if (data[j] < data[minindex]) {
minindex = j;
}
}
if (minindex != i) { // 如果不是无序区的最小值位置不是默认的第一个数据，则交换之。
temp = data[i];
data[i] = data[minindex];
data[minindex] = temp;
}
}
}
归并排序（merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（spanide and conquer）的一个非常典型的应用。
归并操作的过程如下：
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的'序列。
设定两个指针，最初位置分别为两个已经排序序列的起始位置。
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。
重复步骤3直到某一指针达到序列尾。
将另一序列剩下的所有元素直接复制到合并序列尾。
复制代码 代码如下:
public static int[] mergesort(int[] arr) {// 归并排序 --递归
if ( == 1) {
return arr;
}
int half = / 2;
int[] arr1 = new int[half];
int[] arr2 = new int[ - half];
opy(arr, 0, arr1, 0, );
opy(arr, half, arr2, 0, );
arr1 = mergesort(arr1);
arr2 = mergesort(arr2);
return mergesortsub(arr1, arr2);
}
private static int[] mergesortsub(int[] arr1, int[] arr2) {// 归并排序子程序
int[] result = new int[ + ];
int i = 0;
int j = 0;
int k = 0;
while (true) {
if (arr1[i] < arr2[j]) {
result[k] = arr1[i];
if (++i > - 1) {
break;
}
} else {
result[k] = arr2[j];
if (++j > - 1) {
break;
}
}
k++;
}
for (; i < ; i++) {
result[++k] = arr1[i];
}
for (; j < ; j++) {
result[++k] = arr2[j];
}
return result;
}
完整代码（除quicksort）
复制代码 代码如下:
package ng;
import .*;
/**
* 几路常见的排序算法java实现
* @author acer
*
*/
public class commonsort {
/**
* 插入排序具体算法描述如下：
* 1.从第一个元素开始，该元素可以认为已经被排序
* 2.取出下一个元素，在已经排序的元素序列中从后向前扫描
* 3.如果该元素（已排序）大于新元素，将该元素移到下一位置
* 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
* 5.将新元素插入到该位置后
* 6.重复步骤2~5
*/
public static void ionsort(int[] data) {
for (int index = 1; index < ; index++) {
int key = data[index];
int position = index;
// shift larger values to the right
while (position > 0 && data[position - 1] > key) {
data[position] = data[position - 1];
position--;
}
data[position] = key;
}
}
/**
* 希尔排序，算法实现思想参考维基百科；适合大数量排序操作。
*/
staticvoid shellsort(lista) {
int h = 1;
while (h < ()/3) h = h*3 + 1; //: 1, 4, 13, 40, 121, ...
for (; h >= 1; h /= 3)
for (int i = h; i < (); i++)
for (int j = i; j >= h && (j).compareto((j-h)) < 0; j-=h)
(a, j, j-h);
}
/**
* 冒泡排序算法的运作如下：
* 1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
* 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
* 3.针对所有的元素重复以上的步骤，除了最后一个。
* 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。[1]
*/
public static void bubblesort(int[] data) {
int temp = 0;
for (int i = - 1; i > 0; --i) {
boolean issort = false;
for (int j = 0; j < i; ++j) {
if (data[j + 1] < data[j]) {
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
issort = true;
}
}
// 如果一次内循环中发生了交换，那么继续比较；如果一次内循环中没发生任何交换，则认为已经排序好了。
if (!issort)
break;
}
}
/**
* 选择排序的基本思想是：
* 1.遍历数组的过程中，以 i 代表当前需要排序的序号，则需要在剩余的 [i+1…n-1] 中找出其中的最小值，
* 2.然后将找到的最小值与 i 指向的值进行交换。
* 因为每一趟确定元素的过程中都会有一个选择最小值的子流程，所以人们形象地称之为选择排序。
* @param data
*/
public static void selectsort(int[] data) {
int minindex = 0;
int temp = 0;
for (int i = 0; i < ; i++) {
minindex = i; // 无序区的最小数据数组下标
for (int j = i + 1; j < ; j++) { // 在无序区中找到最小数据并保存其数组下标
if (data[j] < data[minindex]) {
minindex = j;
}
}
if (minindex != i) { // 如果不是无序区的最小值位置不是默认的第一个数据，则交换之。
temp = data[i];
data[i] = data[minindex];
data[minindex] = temp;
}
}
}
/**
* 归并操作的过程如下：
* 1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
* 2.设定两个指针，最初位置分别为两个已经排序序列的起始位置
* 3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
* 4.重复步骤3直到某一指针达到序列尾
* 5.将另一序列剩下的所有元素直接复制到合并序列尾
*/
public static int[] mergesort(int[] arr) {// 归并排序 --递归
if ( == 1) {
return arr;
}
int half = / 2;
int[] arr1 = new int[half];
int[] arr2 = new int[ - half];
opy(arr, 0, arr1, 0, );
opy(arr, half, arr2, 0, );
arr1 = mergesort(arr1);
arr2 = mergesort(arr2);
return mergesortsub(arr1, arr2);
}
private static int[] mergesortsub(int[] arr1, int[] arr2) {// 归并排序子程序
int[] result = new int[ + ];
int i = 0;
int j = 0;
int k = 0;
while (true) {
if (arr1[i] < arr2[j]) {
result[k] = arr1[i];
if (++i > - 1) {
break;
}
} else {
result[k] = arr2[j];
if (++j > - 1) {
break;
}
}
k++;
}
for (; i < ; i++) {
result[++k] = arr1[i];
}
for (; j < ; j++) {
result[++k] = arr2[j];
}
return result;
}
private static void printarray(int[] c) {
for (int i = 0; i < ; i++)
(c[i] + ",");
ln();
}
public static void main(string []args){
int[] data = {10,4,9,23,1,45,27,5,2};
ln("bubblesort...");
int[] a = ();
printarray(a);
bubblesort(a);
printarray(a);
ln("selectsort...");
int[] b = ();
printarray(b);
selectsort(b);
printarray(b);
ln("ionsort...");
int[] c = ();
printarray(c);
ionsort(c);
printarray(c);
ln("shellsort...");
listlist = new arraylist();
for(int i=0;i<;i++)
(data[i]);
ln(list);
shellsort(list);
ln(list);
ln("mergesort...");
int[] d = ();
printarray(d);
printarray(mergesort(d));
}
}
s("content_relate");java常见的排序算法的代码相关文章：
1.
冒泡排序算法原理及java实现代码方法
2.java的常见排序方法
3.java堆排序的算法思想的分析
4.c语言快速排序算法及代码
5.冒泡排序的原理以及java代码实现
6.java常用的7大排序算法
7.java简单选择排序算法及实现
8.c语言插入排序算法及实例代码