public class Sort {
public long[] array;
//冒泡排序
public void bublingSort(long[] array) {
int length = array.length;
long temp;
for (int i = length; i > 0; i--) {
for (int j = 0; j < i - 1; j++) {
if (array[j] > array[j + 1]) {
temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
}
}
}
//选择排序
public void selectSort(long[] array) {
int length = array.length;
int k = 0;
long temp;
for (int i = length; i > 0; i--) {
k = 0;
for (int j = 0; j < i - 1; j++) {
if (array[k] < array[j + 1]) {
k = j + 1;
}
if (j == i - 2) {
temp = array[j + 1];
array[j + 1] = array[k];
array[k] = temp;
}
}
}
}
//插入排序
public void insertSort(long[] array) {
int length = array.length;
int in = 0;
long temp;
for (int i = 1; i < length; i++) {
for (int j = 0; j < i; j++) {
if (array[i] < array[j]) {
in = j;
temp = array[i];
while (j < i) {
array[i] = array[i - 1];
i--;
}
array[in] = temp;
}
}
}
}
//希尔排序
public void sortArray(long[] array, int d) {
int length = array.length;
long temp;
for (int i = 0; i < d; i++) {
for (int j = i + d; j < length; j += d) {
temp = array[j];
for (int k = i; k < j; k += d) {
if (array[j] < array[k]) {
int m = j;
while (m > k) {
array[m] = array[m - d];
m = m - d;
}
array[k] = temp;
}
}
}
}
}
public void shellSort(long[] array) {
int length = array.length;
int d = 1;
do {
d = getIncrement(length);
sortArray(array, d);
} while (d > 1);
}
//快速排序
public void recQuickSort(int left, int right) {
if (right - left <= 0) {
return;
} else {
long pivot = array[right];
int partition = partition(left, right, pivot);
recQuickSort(left, partition - 1);
recQuickSort(partition + 1, right);
}
}
public int partition(int left, int right, long pivot) {
int leftPst = left - 1;
int rightPst = right;
while (true) {
while (array[++leftPst] < pivot)
;
while (rightPst > left && array[--rightPst] >= pivot)
;
if (leftPst < rightPst) {
swap(leftPst, rightPst);
} else {
break;
}
}
swap(leftPst, right);
return leftPst;
}
public void swap(int left, int right) {
long temp = array[left];
array[left] = array[right];
array[right] = temp;
}
//归并排序
public void mergeSort(long array[], int left, int right) {
long[] temp = new long[array.length];
sort2(array, temp, left, right);
}
public void sort2(long[] array, long[] temp, int left, int right) {
if (left >= right)
return;
int mid = (left + right) / 2;
sort2(array, temp, left, mid);
sort2(array, temp, mid + 1, right);
int leftPst = left;
int rightPst = mid + 1;
int position = left;
while (leftPst <= mid && rightPst <= right) {
if (array[leftPst] <= array[rightPst]) {
temp[position++] = array[leftPst];
leftPst++;
} else {
temp[position++] = array[rightPst];
rightPst++;
}
}
while (rightPst <= right) {
temp[position++] = array[rightPst];
rightPst++;
}
while (leftPst <= mid) {
temp[position++] = array[leftPst];
leftPst++;
}
System.arraycopy(temp, left, array, left, right - left + 1);
}
public int getIncrement(int d) {
int r = 1;
r = r / 3 + 1;
return r;
}
public void swap(long a, long b) {
long temp = a;
a = b;
b = temp;
}
public void display(long[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
public static void main(String[] args) {
long[] array = { 4, 2, 3, 1, 9, 445, 56, 345, 2, 4354, 67, 23, 56, 234, 678, 3, 1, 7, 90,
43 };
long[] test = {1, 5, 10 ,15, 35, 56, 100, 4, 6, 8, 35, 66, 300, 500};
Sort sort = new Sort();
sort.mergeSort(array, 0, array.length - 1);
sort.display(array);
}
}
public long[] array;
//冒泡排序
public void bublingSort(long[] array) {
int length = array.length;
long temp;
for (int i = length; i > 0; i--) {
for (int j = 0; j < i - 1; j++) {
if (array[j] > array[j + 1]) {
temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
}
}
}
//选择排序
public void selectSort(long[] array) {
int length = array.length;
int k = 0;
long temp;
for (int i = length; i > 0; i--) {
k = 0;
for (int j = 0; j < i - 1; j++) {
if (array[k] < array[j + 1]) {
k = j + 1;
}
if (j == i - 2) {
temp = array[j + 1];
array[j + 1] = array[k];
array[k] = temp;
}
}
}
}
//插入排序
public void insertSort(long[] array) {
int length = array.length;
int in = 0;
long temp;
for (int i = 1; i < length; i++) {
for (int j = 0; j < i; j++) {
if (array[i] < array[j]) {
in = j;
temp = array[i];
while (j < i) {
array[i] = array[i - 1];
i--;
}
array[in] = temp;
}
}
}
}
//希尔排序
public void sortArray(long[] array, int d) {
int length = array.length;
long temp;
for (int i = 0; i < d; i++) {
for (int j = i + d; j < length; j += d) {
temp = array[j];
for (int k = i; k < j; k += d) {
if (array[j] < array[k]) {
int m = j;
while (m > k) {
array[m] = array[m - d];
m = m - d;
}
array[k] = temp;
}
}
}
}
}
public void shellSort(long[] array) {
int length = array.length;
int d = 1;
do {
d = getIncrement(length);
sortArray(array, d);
} while (d > 1);
}
//快速排序
public void recQuickSort(int left, int right) {
if (right - left <= 0) {
return;
} else {
long pivot = array[right];
int partition = partition(left, right, pivot);
recQuickSort(left, partition - 1);
recQuickSort(partition + 1, right);
}
}
public int partition(int left, int right, long pivot) {
int leftPst = left - 1;
int rightPst = right;
while (true) {
while (array[++leftPst] < pivot)
;
while (rightPst > left && array[--rightPst] >= pivot)
;
if (leftPst < rightPst) {
swap(leftPst, rightPst);
} else {
break;
}
}
swap(leftPst, right);
return leftPst;
}
public void swap(int left, int right) {
long temp = array[left];
array[left] = array[right];
array[right] = temp;
}
//归并排序
public void mergeSort(long array[], int left, int right) {
long[] temp = new long[array.length];
sort2(array, temp, left, right);
}
public void sort2(long[] array, long[] temp, int left, int right) {
if (left >= right)
return;
int mid = (left + right) / 2;
sort2(array, temp, left, mid);
sort2(array, temp, mid + 1, right);
int leftPst = left;
int rightPst = mid + 1;
int position = left;
while (leftPst <= mid && rightPst <= right) {
if (array[leftPst] <= array[rightPst]) {
temp[position++] = array[leftPst];
leftPst++;
} else {
temp[position++] = array[rightPst];
rightPst++;
}
}
while (rightPst <= right) {
temp[position++] = array[rightPst];
rightPst++;
}
while (leftPst <= mid) {
temp[position++] = array[leftPst];
leftPst++;
}
System.arraycopy(temp, left, array, left, right - left + 1);
}
public int getIncrement(int d) {
int r = 1;
r = r / 3 + 1;
return r;
}
public void swap(long a, long b) {
long temp = a;
a = b;
b = temp;
}
public void display(long[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
public static void main(String[] args) {
long[] array = { 4, 2, 3, 1, 9, 445, 56, 345, 2, 4354, 67, 23, 56, 234, 678, 3, 1, 7, 90,
43 };
long[] test = {1, 5, 10 ,15, 35, 56, 100, 4, 6, 8, 35, 66, 300, 500};
Sort sort = new Sort();
sort.mergeSort(array, 0, array.length - 1);
sort.display(array);
}
}