排序总结
冒泡排序
原理:每次比较两个相邻的元素,将较大元素交换至右端 特点:每次循环结束,会出现一个排序好的元素,右侧 理解:大的数右移,重复此过程 代码:
public static void bubbleSort(int[] nums){
for (int i=0; i<nums.length-1; i++){ //第i次循环找出第i小的元素0<=i<=length-1
for (int j=0; j<nums.length-1-i; j++){
if (nums[j+1]<nums[j]){
int tmp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = tmp;
}
for (int num : nums) System.out.print(num+"\t");
System.out.println();
}
}
}
优化:使用flag标记是否已经有序
选择排序
原理:每次循环找出最小的元素于左侧,每次循环都从剩余未排序系列找出最小的元素 代码:
/**
* 选择排序
* @param nums
*/
public static void selectSort(int[] nums){
int len = nums.length;
if (len==0 || len==1) return;
for (int i=0; i<len; i++){
for (int j=i+1; j<len; j++){
if (nums[j] < nums[i]){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
}
}
插入排序
原理:递归思想,假设第一个有序,则新插入一个,将其排序,循环递归 代
/**
* 插入排序
* @param nums
*/
public static int[] insertSort(int[] nums, int index){
if (index == nums.length) return nums;
for (int i=0; i<index; i++){
if (nums[index]<nums[i]){
int tmp = nums[index];
nums[index] = nums[i];
nums[i] = tmp;
}
}
return insertSort(nums, index+1);
}
堆排序
原理:利用堆的特性 代码:
/**
* 堆排序
* @param nums
*/
public static void heapSort(int[] nums){
initHeap(nums);
int count = nums.length;
while (count>1){
int tmp = nums[count-1];
nums[count-1] = nums[0];
nums[0] = tmp;
count--;
adjustHeap(nums,count,0);
}
}
public static void initHeap(int[] nums){
for (int root=nums.length/2-1; root>=0; root--){
adjustHeap(nums,nums.length, root);
}
}
public static void adjustHeap(int[] nums, int count, int root){
int maxChildIndex;
while (root<=count/2-1){
if (root==count/2-1 && count%2==0){
maxChildIndex = 2*root+1;
}else {
int leftChildIndex = 2 * root + 1;
int rightChildIndex = 2 * root + 2;
maxChildIndex = nums[leftChildIndex] > nums[rightChildIndex]?leftChildIndex:rightChildIndex;
}
if (nums[root] < nums[maxChildIndex]){
int tmp = nums[root];
nums[root] = nums[maxChildIndex];
nums[maxChildIndex] = tmp;
root = maxChildIndex;
}else {
return;
}
}
}
阅读次数: 本文累计被阅读 1000000 次