1. 选择排序
- 基本思想：
每一次从待排序的数据元素中选择最小的一个元素作为首元素，直到所有元素排完为止。
- 时间复杂度：
O（n平方）
- java 实现
public class Sort {
public static void main(String[] args){
int[] arr={4,9,2,7,6,8,0,1};
selectSort(arr);
for(int i = 0; i<arr.length;i++){
System.out.print(arr[i]);
}
System.out.println("选择排序");
}
/**
* 交换数组元素
* @param arr
* @param a
* @param b
*/
public static void swap(int[] arr, int a, int b){
arr[a] = arr[a] + arr[b];
arr[b] = arr[a] - arr[b];
arr[a] = arr[a] - arr[b];
}
/**
* 选择排序
* @param arr
*/
public static void selectSort(int[] arr){
for(int i = 0; i<arr.length-1; i++){
int min = i;
for(int j = i+1; j < arr.length; j++){
if(arr[j] < arr[min]){
min = j;
}
}
if(min != i){
swap(arr, min, i);
}
}
}
}
2. 冒泡排序
- 基本思想：
对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序。
- 时间复杂度：
O（n平方）
- java 实现
public class Sort {
public static void main(String[] args){
int[] arr={4,9,2,7,6,8,0,1};
bubbleSort(arr);
for(int i = 0; i<arr.length;i++){
System.out.print(arr[i]);
}
System.out.println("冒泡排序");
}
/**
* 交换数组元素
* @param arr
* @param a
* @param b
*/
public static void swap(int[] arr, int a, int b){
arr[a] = arr[a] + arr[b];
arr[b] = arr[a] - arr[b];
arr[a] = arr[a] - arr[b];
}
/**
* 冒泡排序
* @param arr
*/
public static void bubbleSort(int[] arr){
for(int i = 0; i<arr.length-1; i++){
boolean flag = true;
for(int j = 0; j<arr.length-1; j++){
if(arr[j] > arr[j+1]){
swap(arr,j , j+1);
flag = false;
}
}
if(flag){
break;
}
}
}
}
3. 插入排序
- 基本思想：
每一步将一个待排序的记录，插入到前面已经排好序的有序队列中去，直到插完所有元素为止。
- 时间复杂度：
最好情况下，需要比较n-1次，时间复杂度为O(n), 最坏的情况下，倒序，时间复杂度为O（n的平方），随机的时候，比选择、冒泡要好。
- java 实现
public class Sort {
public static void main(String[] args){
int[] arr={4,9,2,7,6,8,0,1};
insertionSort(arr);
for(int i = 0; i<arr.length;i++){
System.out.print(arr[i]);
}
System.out.println("插入排序");
}
/**
* 交换数组元素
* @param arr
* @param a
* @param b
*/
public static void swap(int[] arr, int a, int b){
arr[a] = arr[a] + arr[b];
arr[b] = arr[a] - arr[b];
arr[a] = arr[a] - arr[b];
}
/**
* 插入排序
* @param arr
*/
public static void insertionSort(int[] arr){
for(int i = 1; i<arr.length; i++ ){
int j = 1;
while(j>0 && arr[j]<arr[j-1]){
swap(arr, j , j-1);
j--;
}
}
}
}
4. 希尔排序
- 基本思想：
把记录按下标的一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量减少到1时，整个文件恰好被分成一组，算法便终止。
- 时间复杂度
改进的插入排序，O( n的3/2次方 )
- java 实现
package cxy.six;
public class Sort {
public static void main(String[] args){
int[] arr={4,9,2,7,6,8,0,1};
hillSort(arr);
for(int i = 0; i<arr.length;i++){
System.out.print(arr[i]);
}
System.out.println("希尔排序交换法");
hillMoveSort(arr);
for(int i = 0; i<arr.length;i++){
System.out.print(arr[i]);
}
System.out.println("希尔排序移动法");
}
/**
* 交换数组元素
* @param arr
* @param a
* @param b
*/
public static void swap(int[] arr, int a, int b){
arr[a] = arr[a] + arr[b];
arr[b] = arr[a] - arr[b];
arr[a] = arr[a] - arr[b];
}
/**
* 希尔排序，针对有序序列在插入时采用交换法
* @param arr
*/
public static void hillSort(int[] arr){
for(int gap = arr.length/2; gap >0; gap/= 2){
for(int i = gap; i<arr.length; i++){
int j = i;
while(j-gap>=0 && arr[j]<arr[j-gap]){
swap(arr,j,j-gap);
j-=gap;
}
}
}
}
/**
* 希尔排序，移动法
* @param arr
*/
public static void hillMoveSort(int[] arr){
for(int gap = arr.length/2;gap>0; gap/=2)
for(int i = gap; i<arr.length;i++){
int j =i;
int temp = arr[j];
if(arr[j] < arr[j-gap]){
while(j-gap>=0 && temp<arr[j-gap]){
arr[j] = arr[j-gap];
j-=gap;
}
arr[j] = temp;
}
}
}
}
5. 堆排序
- 基本思想：
将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点，将其与末尾元素进行交换，此时末尾就为最大值，然后将剩余n-1个元素重新构造一个堆，这样就能得到n个元素的次小值，反复，便能得到有序序列。
- 时间复杂度
O （n * n的对数）
- java 实现
package cxy.six;
public class Sort {
public static void main(String[] args){
int[] arr={4,9,2,7,6,8,0,1};
heapSort(arr);
for(int i = 0; i<arr.length;i++){
System.out.print(arr[i]);
}
System.out.println("堆排序");
}
/**
* 交换数组元素
* @param arr
* @param a
* @param b
*/
public static void swap(int[] arr, int a, int b){
arr[a] = arr[a] + arr[b];
arr[b] = arr[a] - arr[b];
arr[a] = arr[a] - arr[b];
}
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);
}
}
/**
* 调整堆
* @param arr
* @param i
* @param length
*/
public static void adjustHeap(int[] arr, int i, int length){
int temp = arr[i];
for(int k=i*2+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;
}
}
运行结果：
