一、冒泡排序
1、基本思想:依次比较相邻两个数,小的在前,大的在后 2、动态效果图 3、代码实现
private static void bubbleSort(int[] arr){
boolean flag=false;
int temp=0;
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
flag=true;
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
if(!flag){
break;
}
}
}
二、选择排序
1、基本思想:在序列中找到最小元素,放在第一个位置;从剩余未排序元素中继续找到最小的元素,放在第二个位置…以此类推,直到排序完毕。 2、动态效果图 3、代码实现
private static void selectSort(int[] arr){
for(int i=0;i<arr.length-1;i++){
int minIndex = i;
int min = arr[minIndex];
for(int j = 1 + i;j<arr.length;j++){
if(min > arr[j]){
min = arr[j];
minIndex = j;
}
}
arr[minIndex] = arr[i];
arr[i] = min;
}
}
三、插入排序
1、基本思想:把n个待排序的元素第一位看成有序表,其它的看成无序表,排序过程中,每次从无序表中取出一个数,依次与有序表中的数进行比较,插入到合适的位置。 2、动态效果图
3、代码实现
public static void insertSort(int[] arr ){
int insertVal = 0;
int insertIndex = 0;
for (int i = 1; i < arr.length; i++) {
insertVal = arr[i];
insertIndex = i - 1;
while(insertIndex >= 0 && insertVal < arr[insertIndex]){
arr[insertIndex+1] = arr[insertIndex];
insertIndex--;
}
if(insertIndex + 1 != i){
arr[insertIndex+1] = insertVal;
}
}
}
四、希尔排序
1、基本思想:希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序。它与插入排序的不同之处在于,它会优先比较较远的元素。 2、效果图 3、代码实例 a.冒泡版希尔排序
public static void shellSort(int[] arr) {
for(int step = arr.length/2;step > 0;step /= 2) {
for(int i = step;i < arr.length;i++) {
for(int j = i - step;j >= 0;j -= step) {
if(arr[j] > arr[j + step]) {
int temp = arr[j];
arr[j] = arr[j + step];
arr[j + step] = temp;
}
}
}
}
}
b.插入版希尔排序
public static void shellSort(int[] arr){
for(int step=arr.length/2;step>0;step/=2){
for(int i=step;i<arr.length;i++){
int j=i;
int temp=arr[j];
if(arr[j]<arr[j-step]){
while(j-step>=0&&temp<arr[j-step]){
arr[j]=arr[j-step];
j-=step;
}
arr[j]=temp;
}
}
}
}
五、快速排序
1、基本思想:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录进行排序,以达到整个排序的过程。 2、效果图 思路:使用分治法把一个串分为两个子串;找一个基准点,暂时选中间点为基准点;重新排序数列,比基准值小的放在基准点前面,大的放在后面;递归的把小于基准值的子数列和大于基准值的子数列排序。 3、代码实现
public static void quickSort(int[] arr,int left,int right){
int l = left;
int r = right;
int pivot = arr[(left + right) / 2];
int temp = 0;
while(l < r) {
while(arr[l] < pivot) {
l += 1;
}
while(arr[r] > pivot) {
r -= 1;
}
if(l >= r) {
break;
}
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
if(arr[l] == privot) {
r -= 1;
}
if(arr[r] == privot) {
l += 1;
}
}
if(l == r) {
l += 1;
r -= 1;
}
if(left < r) {
quickSort(arr,left,r);
}
if(right > l) {
quickSort(arr,l,right);
}
}
六、归并排序
1、基本思想:采用经典的分治策略,分治法将问题分成一些小的问题然后递归解决,则治的阶段就是将分的阶段得到的答案综合在一起,分而治之。 2、效果图
3、代码实现
public static void mergerSort(int[] arr,int left,int right,int[] temp){
if(left<right){
int middle = (left + right)/2;
mergerSort(arr,left,middle,temp);
mergerSort(arr,middle + 1,right,temp);
merger(arr, left, middle, right, temp);
}
}
public static void merger(int[] arr,int left,int middle,int right,int[] temp){
int i = left;
int j = middle + 1;
int t = 0;
while (i <= middle && j <= right) {
if(arr[i] <= arr[j]){
temp[t] = arr[i];
t++;
i++;
}else {
temp[t] = arr[j];
t++;
j++;
}
}
while (i <= middle){
temp[t] = arr[i];
t++;
i++;
}
while (j <= right){
temp[t] = arr[j];
t++;
j++;
}
t = 0;
int tempLeft = left;
while (tempLeft <= right){
arr[tempLeft] = temp[t];
t++;
tempLeft++;
}
}
七、基数排序
1、基本思想:将所有带比较数值统一为同样的数位长度,数据较短的数前面补0,然后从最低位开始依次进行依次排序,这样从最低位排序一直到最高位排序完成之后,数列就变成了一个有序序列。 2、代码实现
public static void radixSort(int arr[]){
System.out.println("基数排序,arr长度:"+arr.length);
int max = arr[0];
for(int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
int maxLength = (max + "").length();
int[][] bucket = new int[10][arr.length];
int[] bucketElementCounts = new int[10];
for(int i = 0 , n = 1; i < maxLength; i++, n *= 10) {
for(int j = 0; j < arr.length; j++) {
int digitOfElement = arr[j] / n % 10;
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
int index = 0;
for(int k = 0; k < bucketElementCounts.length; k++) {
if(bucketElementCounts[k] != 0) {
for(int l = 0; l < bucketElementCounts[k]; l++) {
arr[index++] = bucket[k][l];
}
}
bucketElementCounts[k] = 0;
}
}
}
八、堆排序
1、基本思想 大顶堆:每个节点的值都大于或者等于它的左右子节点的值。 小顶堆:每个节点的值都小于或者等于它的左右子节点的值。 2、效果图 3、思路(大根堆) a.首先将待排序的数组构造成一个大根堆,此时,整个数组的最大值就是堆结构的顶端 b.将顶端的数与末尾的数交换,此时,末尾的数为最大值,剩余待排序数组个数为n-1 c.将剩余的n-1个数再构造成大根堆,再将顶端数与n-1位置的数交换,如此反复执行,便能得到有序数组 注意:升序用大根堆,降序就用小根堆(默认为升序) 4、代码实现 大根堆
package Sort;
import java.util.Arrays;
public class HeapSort {
public static void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i];
for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
if (k + 1 < length && arr[k] < arr[k + 1]) {
k++;
}
if (arr[k] > temp) {
arr[i] = arr[k];
i = k;
} else {
break;
}
}
arr[i] = temp;
}
public static void swap(int[] arr,int a,int b) {
int temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
public static void heapsort(int[] arr) {
for(int i=arr.length/2-1;i>=0;i--) {
adjustHeap(arr,i,arr.length);
}
for(int j=arr.length-1;j>0;j--) {
swap(arr,0,j);
adjustHeap(arr,0,j);
}
}
public static void main(String[] args) {
int[] arr= {2,10,8,22,34,5,12,28,21,11};
System.out.println("堆排序前:");
System.out.println(Arrays.toString(arr));
heapsort(arr);
System.out.println("堆排序后:");
System.out.println(Arrays.toString(arr));
}
}
小根堆
package Sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class HeapSort {
public static void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i];
for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
if (k + 1 < length && arr[k] > arr[k + 1]) {
k++;
}
if (arr[k] < temp) {
arr[i] = arr[k];
i = k;
} else {
break;
}
}
arr[i] = temp;
}
public static void swap(int[] arr,int a,int b) {
int temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
public static void heapsort(int[] arr) {
for(int i=arr.length/2-1;i>=0;i--) {
adjustHeap(arr,i,arr.length);
}
for(int j=arr.length-1;j>0;j--) {
swap(arr,0,j);
adjustHeap(arr,0,j);
}
}
public static void main(String[] args) {
int[] arr= {2,10,8,22,34,5,12,28,21,11};
System.out.println("堆排序前:");
System.out.println(Arrays.toString(arr));
heapsort(arr);
System.out.println("堆排序后:");
System.out.println(Arrays.toString(arr));
}
}
|