多种排序算法代码
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了多种排序算法代码，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5472字，纯文字阅读大概需要8分钟。
内容图文
冒泡排序 O(n²)
public static void bubbleSort(int[] array){
int length = array.length;
if(length <= 1){
return;
}
for(int i = 0; i < length; i++){
boolean flag = true;
for(int j = 0; j <length - i - 1; j++){
if(array[j] > array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
flag = false;
}
}
if(flag){
break;
}
}
}
插入排序 O(n²)
public static void insertionSort(int[] arr){
int len = arr.length;
if(len <= 1){
return;
}
for(int i = 1; i < len; i++){
int current = arr[i];
int preIndex = i - 1;
while(preIndex >= 0 && arr[preIndex] > current){
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
}
选择排序（不稳定） O(n²)
public static void selectionSort(int[] arr){
int len = arr.length;
if(len <= 1){
return;
}
for(int i = 0; i < len; i++){
int minIndex = i;
for(int j = i; j < len; j++){
if(arr[minIndex] > arr[j]){
minIndex = j;
}
}
int current = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = current;
}
}
归并排序 O(n*log(n))
拆分（排序实现函数）
public static int[] mergeSort(int[] arr){
if(arr.length < 2){
return arr;
}
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr,0,mid);
int[] right = Arrays.copyOfRange(arr,mid,arr.length);
return merge(mergeSort(left),mergeSort(right));
}
合并（在排序函数中调用）
public static int[] merge(int[] left,int[] right){
int[] newArray = new int[left.length+right.length];
int lindex = 0;
int rindex = 0;
for(int i = 0; i < newArray.length; i++){
if(lindex >= left.length){
newArray[i] = right[rindex++];
}else if(rindex >= right.length){
newArray[i] = left[lindex++];
}else if(left[lindex] < right[rindex]){
newArray[i] = left[lindex++];
}else{
newArray[i] = right[rindex++];
}
}
return newArray;
}
快速排序(不稳定) O(n*log(n))
//排序
public static void quickSort(int[] arr,int begin,int end){
//递归终止条件
if(arr.length <= 1 || begin >= end){
return;
}
//进行分区得到分区下标
int pivotlndex = partition(arr,begin,end);
//递归左侧快排
quickSort(arr,begin,pivotlndex-1);
//递归右侧快排
quickSort(arr,pivotlndex+1,end);
}
//基准点
private static int partition(int[] arr,int begin,int end){
int pivot = arr[end];
int piovtIndex = begin;
for(int i = begin; i < end; i++){
if(arr[i] < pivot){
if(i > piovtIndex){
swap(arr,i, piovtIndex);
}
piovtIndex++;
}
}
swap(arr, piovtIndex,end);
return piovtIndex;
}
//交换方法
private static void swap(int[] arr,int i,int j){
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
桶排序 O(n)
package sort;
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
//O(n)
public class BucketSort {
/**
* 桶排序
* @param array 待排序序列
* @param bucketSize 桶中元素类型的个数即每个桶所能放置多少个不同数值
* （例如bucketSize==5时，该桶可以存放{1,2,3,4,5}这几种数字，但是容量不限，既可以存放100个3）
* @return 排序好的集合
*/
public List<Integer> bucketSort(List<Integer> array,int bucketSize){
//合法性效验
if(array == null || array.size() < 2 || bucketSize < 1){
return array;
}
//找出我们集合中的元素的最大值和最小值
int max = array.get(0);
int min = array.get(0);
for(int i = 0; i < array.size(); i++){
if(array.get(i) > max){
max = array.get(i);
}
if(array.get(i) < min){
min = array.get(i);
}
}
//计算桶的个数
int bucketCount = (max - min) / bucketSize + 1;
//按照顺序创建桶，创建一个list，list带下标是有序的，list中每一个元素是一个桶，也用list桶表示
List<List<Integer>> bucketList = new ArrayList<>();
for(int i = 0; i < bucketCount; i++){
bucketList.add(new ArrayList<Integer>());
}
//将待排序的集合依次添加到对应的桶中
for(int j = 0; j < array.size(); j++){
int bucketIndex = (array.get(j) - min) / bucketSize;
bucketList.get(bucketIndex).add(array.get(j));
}
//桶内元素的排序(使用递归桶排序)
List<Integer> reustList = new ArrayList<>();
for(int j = 0; j < bucketList.size(); j++){
List<Integer> everyBucket = bucketList.get(j);
if(everyBucket.size() > 0){
if(bucketCount == 1){
bucketSize--;
}
List<Integer> temp = bucketSort(everyBucket,bucketSize);
for(int i = 0; i < temp.size(); i++){
reustList.add(temp.get(i));
}
}
}
return reustList;
}
/**
* 测试用例
*/
@Test
public void testBucketSort(){
List<Integer> list = new ArrayList<>();
list.add(5);
list.add(2);
list.add(2);
list.add(6);
list.add(9);
list.add(0);
list.add(3);
list.add(4);
System.out.println(list);
List<Integer> bucketSort = bucketSort(list, 2);
System.out.println(bucketSort);
}
}
计数排序 O(n)
package sort;
import org.junit.Test;
import java.util.Arrays;
public class CountingSort {
public void countingSort(int[] array) {
//求出待排序的数组中的最大值和最小值，找出取值区间
int max = array[0];
int min = array[0];
for (int i = 0; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
if (array[i] < min) {
min = array[i];
}
}
//定义一个额外的数组
int bucketSize = (max - min) + 1;
int[] bucket = new int[bucketSize];
//统计对应元素的个数
for (int i = 0; i < array.length; i++) {
int bucketIndex = array[i] - min;
bucket[bucketIndex] += 1;
}
//对数组中的元素进行累加操作
for (int i = 1; i < bucket.length; i++) {
bucket[i] = bucket[i] + bucket[i - 1];
}
//创建一个临时数组，存储最终有序的序列
int[] temp = new int[array.length];
//逆序扫描待排序的数组，可以保证我们元素的稳定性
for (int i = array.length - 1; i >= 0; i--) {
int bucketIndex = array[i] - min;
temp[bucket[bucketIndex]-1] = array[i];
bucket[bucketIndex] -= 1;
}
//将我们临时数据依次放入原始数组中
for(int i = 0; i < temp.length; i++){
array[i] = temp[i];
}
}
//测试用例
@Test
public void testCountingSort(){
int[] array = new int[8];
array[0] = 5;
array[1] = 2;
array[2] = 6;
array[3] = 9;
array[4] = 0;
array[5] = 3;
array[6] = 3;
array[7] = 4;
System.out.println(Arrays.toString(array));
countingSort(array);
System.out.println(Arrays.toString(array));
}
}
内容总结
以上是互联网集市为您收集整理的多种排序算法代码全部内容，希望文章能够帮你解决多种排序算法代码所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】