排序浅谈 - 黑马程序员技术交流社区

class SortMethod{
/**
打印一个数组
*/
public static void listPriter(int[] arr){
for(int e: arr){
System.out.println(e);
}
}
/**
生成一个不含重复元素的从(0-n)的随机int数组
*/
public static int [] randList0 (int n)
{
int [] randNum = new int [n];
int [] unUsed = new int [n];
for (int u = 0; u < n; u++)
{
unUsed[u] = u+1;
}
for (int i = 0; i < n; i++)
{
double positionDouble = Math.random() * (n-1-i);
int position = (int) positionDouble;
randNum[i] = unUsed[position];
unUsed[position] = unUsed[n-1-i];
}
return randNum;
}
/**
生成一个包含重复元素的从(0-n)的随机int数组
*/
public static int [] randList1 (int n)
{
int [] randNum = new int[n];
// Random r = new Random();
for (int i = 0; i < n; i++)
{
double numDouble = Math.random() * (n-1-i);
int num = (int) numDouble;
randNum[i] = num;
}
return randNum;
}
/**
选择排序法
时间复杂度为O(N^2)
*/
public static int [] selectionSort(int [] unSortedArr){
int [] sortedArr = unSortedArr;
//外层循环遍历数组各元素
for (int i = 0; i < sortedArr.length ;i++){
int min =i;
//内层循环将外层循环所遍历到的元素和数组中其它为排序的元素进行大小比较
for(int j =i ; j< sortedArr.length;j ++){
if (sortedArr[min] > sortedArr[j]){
min = j;
}
}
//比较后得出未排序数组中的最小值，将其写入到排序数组的前部
int temp = sortedArr[i];
sortedArr[i] = sortedArr[min];
sortedArr[min] = temp;
}
return sortedArr;
}
/**
冒泡排序法
时间复杂度为O(N^2)
*/
public static int [] bubbleSort(int [] unSortedArr){
//外层循环遍历数组各元素
for (int i = 0; i < unSortedArr.length ; i++ ){
//内层循环将外层循环所遍历到的元素和其相邻的后一位数组进行大小比较
for(int j = 0; j < unSortedArr.length-i-1; j++){
if(unSortedArr[j]>unSortedArr[j+1]){
//比较后，相对较大的元素置于相对靠后的位置
int temp = unSortedArr[j];
unSortedArr[j] = unSortedArr[j+1];
unSortedArr[j+1] = temp;
}
}
}
return unSortedArr;
}
/**
快速排序法
时间复杂度为O(NlogN)
*/
public static int [] QuickSort(int [] unSortedArr, int startIndex, int endIndex){
//先选取基准值为最后一个元素的大小。同时设置数组排序的起始及终止角标
int pivot = endIndex;
int l = startIndex;
int h = endIndex;
while(l<h){
//遍历时末端角标往前移一位
h--;
//通过while循环从数组后端 h 至数组前端 l 遍历，若被遍历的元素小于基准值，
// 则将其移动到数组前端，同时前端 l 角标增一位。
while(l<h&&unSortedArr[pivot]>unSortedArr[h]){
int temp0 = unSortedArr[l];
unSortedArr[l] = unSortedArr[h];
unSortedArr[h] = temp0;
l++;
}
}
// 循环遍历完后 l=h ，还剩下角标为 l 的元素未和基准值比对过大小。
// 同时基准值位于数组最末端，这时我们需要将它移动到数组中间。
if(unSortedArr[pivot]>unSortedArr[l]){
int temp1 = unSortedArr[l+1];
unSortedArr[l+1] = unSortedArr[pivot];
unSortedArr[pivot] = temp1;
pivot = l+1;
}else{
int temp2 = unSortedArr[l];
unSortedArr[l] = unSortedArr[pivot];
unSortedArr[pivot] = temp2;
pivot = l;
}
// 最后将大于基准值与小于基准值的两个数组部分通过递归进行传递排序
if(pivot-1>startIndex)
QuickSort(unSortedArr,startIndex,pivot-1);
if(endIndex>pivot+1)
QuickSort(unSortedArr,pivot+1,endIndex);
return unSortedArr;
}
/**
哈希排序法(模拟)
先找出数组中的最大值和最小值，创建一个max-min长度的临时寄存数组，
遍历待排序数组，将遍历到的数组元素放入下标与其值相等的临时寄存数组中(临时寄存数组对应下标的元素的值+1)，
待遍历完原数组后，对临时寄存数组进行遍历。若数组中值为n，则说明原数组中有n个大小为数组下标+min的元素。
将这些元素按顺序添加入一个新数组中，这个新数组就是一个排序好的数组。
时间复杂度为O(N)
*/
public static int [] hashSort(int [] unSortedArr){
int max = unSortedArr[0];
int min = unSortedArr[0];
int [] sortedArr = new int [unSortedArr.length];
// 通过for循环找到最大值和最小值
for (int i =0; i< unSortedArr.length; i++){
if(unSortedArr[i]>max)
max = unSortedArr[i];
if(unSortedArr[i]<min)
min = unSortedArr[i];
}
// 定义储存元素的临时数组，数组的大小为最大值至最小值的范围
int [] sortTemp = new int[max-min+1];
// 通过for循环遍历未排序的原数组，将遍历到的数组元素放入下标与其值相等的临时寄存数组中
for(int i = 0; i<unSortedArr.length; i++){
sortTemp[unSortedArr[i]-min] += 1;
}
//定义数组指针
int index = 0;
//通过for循环将临时数组中的元素顺序取出，存入新的数组中，既是排序好的数组
for(int i = 0; i<sortTemp.length; i++){
for(int j = 0; j<sortTemp[i]; j++){
sortedArr[index] = i+min;
index++;
}
}
return sortedArr;
}
}

复制代码