Java常用排序算法

冒泡排序

冒泡排序每次比较相邻两个元素的值并判断是否交换

1
2
3
4
5
6
7
8
9
10
11
12
public static int [] bubbleSort(int [] nums){
int len = nums.length;
for (int i = 0;i<len;i++){
for(int j = 0;j < len - 1 - i ; j++){
if (nums[j]>nums[j+1]){
int temp = nums[j];
nums[j] = nums[j+1];
nums [j+1] = temp;
}
}
}
}

快速排序

快速排序随意选择一个mid值,小于mid放在mid前,大于mid放在mid后,在循环进行此过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int getMidIndex(int [] nums,int low,int high){
int temp = nums[low];
while(low < high){
while(low < high && nums[high]>=temp){
high--;
}
nums [low] = nums[high];
while(low < high && nums[low]<= temp){
low++;
}
nums[high] = nums[low]
}
nums[low] = temp;
return low;
}
1
2
3
4
5
6
7
public static void quickSort(int []nums,int low,int high){
if(low<high){
int mid = getMidIndex(nums,low,high);
quickSort(nums,low,mid-1);
quickSort(nums,mid+1,high)
}
}

选择排序

选择排序每次选择剩余数字中最小的放在已排序的最后面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void selectSort(int [] nums){
int len = nums.length;
for (int i=0;i<len;i++){
int k = i;
for (int j = i;j<len;j++){
if(nums[j]<nums[k]){
k = j;
}
}
int temp = nums[i];
nums[i] = nums[k];
nums[k] = temp;
}
}

插入排序

依次将数组中剩余数组插入到已排序数组中,第一个数字可认为已排序好

1
2
3
4
5
6
7
8
9
10
11
12
public static void insertSort(int [] nums){
int len = nums.length;
for(int i=1;i<len;i++){
int temp = nums[i];
int k = i;
while(k>0 && temp < nums[k-1]){
nums[k] = nums [k-1];
k--;
}
nums[k] = temp;
}
}

希尔排序

希尔排序是加强版的插入排序,将元素分组 {0,0+increament,0+2increament,0+3increamen}、{1,1+increament,1+2increament,1+3increament…},在每个组内进行排序,依次减小increament直到为1,为1时即对整个数组进行插入排序(只有一个组{0,0+1,0+2,0+3…})

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void shellSort(int []nums){
for(int increament = nums.length/2; increament>0; increament/=2){
//从increament开始,[0,increament-1]中每一个均当做第一个元素,已排好
for(int i = increament;i<nums.length;i++){
int temp = nums[i];
int j;
//插入排序:插入元素i
for(j = i;j>=increamrnt;j-=increament) {
if(temp<nums[j-increament]){
nums [j] = nums[j-increament];
}else{
break;
}
}
nums[j] = temp;
}
}
}

归并排序

将元素看为数组,依次合并两个数组,直到只有一个数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public static int [] mergeSort(int []nums,int low,int high){
if(low<high){
int mid = (low+high)>>1;
mergeSort(nums,low,mid);
mergeSort(nums,mid+1,high);
merge(nums,low,high);
}
return nums;
}
public static void merge(int []nums,int low,int high){
int result [] = new int[high-low+1];
int mid = (low+high)>>1;
int k = 0;
int p1 = low; //左边数组指针
int p2 = mid+1; //右边数组指针
//合并数组
while(p1<=mid&&p2<=high){
if(nums[p1]>nums[p2]){
result[k++] = nums[p2++];
}else{
result[k++] = nums [p1++];
}
}
while(p1<=mid){
result[k++] = nums[p1++];
}
while(p2<=high){
result[k++] = nums[p2++];
}
int key = 0;
for(int i = low;i<=high;i++){
nums[i] = result[key++];
}
}

堆排序

堆排序将数组看做二叉树,构造顶大堆,找到最大值,将其放在末位,再将剩余的数看做二叉树,接着找最大,放在当前的末位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public static void heapSort(int []nums){
for(int i = 0;i<nums.length-1;i++){
int lastIndex = nums.length-1-i;
buildMaxHeap(nums,lastIndex);
int temp = nums[0];
nums[0] = nums[lastIndex];
nums[lastIndex] = temp;
}
}
public static void buildMaxHeap(int []nums,int lastIndex){
//从有子节点的节点开始
for(int i = (lastIndex-1)/2;i>=0;i--){
int k = i;
while(k*2+1<=lastIndex){
int biggerIndex = k*2+1;
if(biggerIndex<lastIndex){
if(nums[biggerIndex]<nums[biggerIndex+1]){
biggerIndex++;
}
}
//判断父节点是否小于子节点,交换
if(nums[k]<nums[biggerIndex]){
int temp = nums[k];
nums[k] = nums[biggerIndex];
nums[biggerIndex] = temp;
k = biggerIndex;
}else{
break;
}
}
}
}