package Sort;
public class TestDemo01 {
public static void main(String[] args) {
int a[] = {2, 4, 6, 1, 7, 5};
// sort(a); //直接插入排序
// sort2(a); //直接插入排序
// sort3(a); //希尔排序
// sort4(a); //简单选择排序
// sort5(a); //冒泡排序
// sort6(a, 0, a.length - 1); //快速排序
// sort7(a, 0, a.length - 1); //归并排序
// sort8(a); //堆排序
for(int i = 0; i < a.length; i++){
System.out.print(a[i]+ " ");
}
}
/**
* 直接插入排序
* 通过交换进行插入排序，借鉴冒泡排序
* @param a
*/
public static void sort(int a[]){
int length = a.length;
for(int i = 0; i < length - 1; i++){
for(int j = i + 1; j > 0; j--){
if(a[j] < a[j-1]){
int temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
}
/**
* 直接插入排序
* 通过将较大的元素都向右移动而不总是交换两个元素
* @param a
*/
public static void sort2(int a[]){
for(int i = 1; i < a.length; i++){
int num = a[i];
int j;
for(j = i-1; j >= 0; j--){
if(a[j] > num){
a[j+1] = a[j];
}else{
break;
}
}
a[j+1] = num;
}
}
/**
* 希尔排序
* @param a
*/
public static void sort3(int a[]){
int length = a.length;
int h = 1;
while(h < length/3) h = 3*h +1;
for( ; h >= 1; h /= 3){
for(int i = 0; i < length - h; i += h){
for(int j = i+h; j > 0; j -= h){
if(a[j] < a[j-h]){
int temp = a[j];
a[j] = a[j-h];
a[j-h] = temp;
}
}
}
}
}
/**
* 简单选择排序
* @param a
*/
public static void sort4(int a[]){
for(int i = 0; i < a.length; i++){
int min = i;
//选出之后待排序中值最小的位置
for(int j = i + 1; j < a.length; j++){
if(a[j] < a[min]){
min = j;
}
}
//最小值不等于当前值时进行交换
if(min != i){
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
}
/**
* 冒泡排序
* @param a
*/
public static void sort5(int a[]){
//外层循环控制比较的次数
for (int i = 0; i < a.length - 1; i++) {
//内层循环控制到达位置
for (int j = 0; j < a.length - i - 1; j++) {
//前面的元素比后面大就交换
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
/**
* 快速排序
* @param a
* @param low
* @param high
*/
public static void sort6(int a[], int low, int high){
//已经排完
if(low >= high){
return;
}
int left = low;
int right = high;
//保存基准值
int pivot = a[left];
while(left < right){
//从后向前找到比基准小的元素
while(left < right && a[right] >= pivot)
right--;
a[left] = a[right];
//从前往后找到比基准大的元素
while(left < right && a[left] <= pivot)
left++;
a[right] = a[left];
}
a[left] = pivot;
sort6(a, low, left - 1);
sort6(a, left + 1, high);
}
/**
* 归并排序
* @param a
* @param low
* @param high
*/
public static void sort7(int a[], int low, int high){
if(low >= high){
return;
}
int mid = (low + high) / 2;
//左半边排序
sort7(a, low, mid);
//右半边排序
sort7(a, mid+1, high);
//归并
merge(a, low, mid, high);
}
/**
* 归并
* @param a
* @param low
* @param mid
* @param high
*/
public static void merge(int a[], int low, int mid, int high){
int aux[] = new int[a.length];
int i;
int j;
int k;
for(k = low; k <= high; k++){
aux[k] = a[k];
}
for(i = low, j = mid + 1, k = low; i <= mid && j <= high; k++){
if(aux[i] < aux[j]){
a[k] = aux[i];
i++;
}else{
a[k] = aux[j];
j++;
}
}
while(i <= mid) a[k++] = aux[i++];
while(j <= high) a[k++] = aux[j++];
}
/**
* 堆排序
* @param a
*/
public static void sort8(int a[]){
for(int i = a.length-1; i > 0; i--){
max_heapify(a, i);
//堆顶元素(第一个元素)与Kn交换
int temp = a[0];
a[0] = a[i];
a[i] = temp;
}
}
public static void max_heapify(int a[], int n){
int child;
for(int i = (n-1)/2; i >= 0; i--){
//左子节点位置
child = 2 * i + 1;
//右子节点存在且大于左子节点，child变成右子节点
if (child != n && a[child] < a[child + 1]) {
child++;
}
//交换父节点与左右子节点中的最大值
if (a[i] < a[child]) {
int temp = a[i];
a[i] = a[child];
a[child] = temp;
}
}
}
}
参考: https://www.cnblogs.com/morethink/p/8419151.html
网友评论