java常用排序算法 java各种排序算法优质

人的记忆力会随着岁月的流逝而衰退,写作可以弥补记忆的不足,将曾经的人生经历和感悟记录下来,也便于保存一份美好的回忆。范文怎么写才能发挥它最大的作用呢?以下是小编为大家收集的优秀范文,欢迎大家分享阅读。

java常用排序算法 java各种排序算法篇一

一个排序算法是稳定的,就是当有两个相等记录的关键字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语言插入排序算法及实例代码

声明:准根文档网所有作品(图片、文字)均由用户自行上传分享,仅供网友学习交流。若您的权利被侵害,请联系 saizw@outlook.com