几种排序算法的java实现_IT岛 | www.IT-dao.com

几种排序算法的java实现

时间:2011-09-14 11:29 来源:未知作者:admin 点击: 次

【内容简介】数组的排序方法有很多，效率也各不相同，下面简单介绍一下几种常见的排序算法。 1.选择排序法：将要排序的数组分成两部分，一部分是从大到小已经排好序的，一部分是无序的，从无序的

数组的排序方法有很多，效率也各不相同，下面简单介绍一下几种常见的排序算法。

1.选择排序法：将要排序的数组分成两部分，一部分是从大到小已经排好序的，一部分是无序的，从无序的部分取出最小的放到已经排序的最后面。实现如下：

public int[] choiceSort(int[] arr){

for(int i = 0;i < arr.length;i++){

int m = i;

for(int j = i + 1;j < arr.length;j++){

//如果第j个元素比第m个元素小，将j赋值给m

if(arr[j] < arr[m]){

m = j;

}

//交换m和i两个元素的位置

if(i != m){

int t = arr[i];

arr[i] = arr[m];

arr[m] = t;

}

return arr;

}

2.冒泡排序法：冒泡排序的思路就不用介绍了。上实现：

public int[] bubbleSort(int[] arr){

for(int i = 0;i < arr.length;i++){

//比较两个相邻的元素

for(int j = 0;j < arr.length-i-1;j++){

if(arr[j] > arr[j+1]){

int t = arr[j];

arr[j] = arr[j+1];

arr[j+1] = t;

}

return arr;

}

3.插入排序法：将要排序的数组分成两部分，每次从后面的部分取出索引最小的元素插入到前一部分的适当位置。基本实现如下：

public int[] insertSort(int[] arr){

for(int i = 1;i < arr.length;i++){

int temp = arr[i];

int j = i - 1;

while(temp < arr[j]){

arr[j+1] = arr[j];

j--;

if(j == -1){

break;

}

arr[j+1] = temp;

}

return arr;

}

3.快速排序法：快速排序法号称是目前最优秀的算法之一，实现思路是，将一个数组的排序问题看成是两个小数组的排序问题，而每个小的数组又可以继续看成更小的两个数组，一直递归下去，直到数组长度大小最大为2。实现如下：

public int[] fastSort(int[] arr,int left,int right){

if(left < right){

int s = arr[left];

int i = left;

int j = right + 1;

while(true){

//向右找大于s的元素的索引

while(i+1 < arr.length && arr[++i] < s);

//向左找小于s的元素的索引

while(j-1 > -1 && arr[--j] > s);

//如果i >= j 推出循环

if(i >= j){

break;

}else{

//教化i和j位置的元素

int t = arr[i];

arr[i] = arr[j];

arr[j] = t;

}

arr[left] = arr[j];

arr[j] = s;

//对左面进行递归

fastSort(arr,left,j-1);

//对右面进行递归

fastSort(arr,j+1,right);

}

return arr;

}

顶一下

(0)

踩一下

(0)