• 发表于 2年前
• 阅读 40
• 收藏 7
• 评论 0

# 排序算法

### 冒泡排序

``````private static void pop(int[] array){
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if(array[j] < array[j + 1]){
swap(j + 1, j, array);
}
}
}
}
``````

### 选择排序

``````private static void select(int[] array){
for (int i = 0; i < array.length; i++) {
for (int j = i; j < array.length; j++) {
if(array[i] < array[j]){
swap(j, i, array);
}
}
}
}
``````

### 插入排序

``````private static void insert(int[] array){
for (int i = 0; i < array.length; i++) {
for (int j = i; j > 0; j--) {
if(array[j - 1] < array[j]){
swap(j - 1, j, array);
}
}
}
}
``````

### 归并排序

``````private static void merge(int[] array){
int[] temp = new int[array.length];
mergeCore(0, array.length - 1, temp, array);
}

private static void mergeCore(int left, int right, int[] temp, int[] array) {
if(left == right){
return;
}else{
int mid = (left + right) / 2;

mergeCore(left, mid, temp, array);
mergeCore(mid + 1, right, temp, array);

mergeTogether(left, mid, right, temp, array);
}
}

private static void mergeTogether(int left, int mid, int right, int[] temp, int[] array) {
int curTemp = 0;
int curLeft = left;
int curRight = mid + 1;
int size = right - left;
while(curLeft <= mid && curRight <= right){
if(array[curLeft] >= array[curRight]){
temp[curTemp++] = array[curLeft++];
}else{
temp[curTemp++] = array[curRight++];
}
}

while(curLeft <= mid){
temp[curTemp++] = array[curLeft++];
}

while(curRight <= right){
temp[curTemp++] = array[curRight++];
}

for (int i = 0; i <= size; i++) {
array[left++] = temp[i];
}
}
``````

### 希尔排序

``````private static void shell(int[] array){
int salt = 1;
while(salt < array.length / 3){
salt = salt * 3 + 1;
}

while(salt > 0){
for (int i = salt; i < array.length; i++) {
for (int j = i ; j > salt - 1; j = j - salt) {
int t;
if(array[j - salt] < array[j]){
swap(j - salt, j, array);
}
}

}
salt = (salt - 1)/3;
}
}
``````

### 快速排序

``````private static void fast(int[] array){
fastCort(0, array.length - 1, array);
}

private static int calcMid(int left, int right, int[] array) {
int mid = (left + right)/2;
if(array[left] < array[mid]){
swap(left, mid, array);
}
if(array[left] < array[right]){
swap(left, right, array);
}
if(array[mid] < array[right]){
swap(mid, right, array);
}
swap(mid,right - 1, array);
return 0;
}

private static void fastCort(int left, int right, int[] array) {
if(left < right){
int pivot = array[right];
int border = findBorder(left, right, pivot, array);
fastCort(left, border - 1, array);
fastCort(border + 1, right, array);
}else{
return;
}
}

private static int findBorder(int left, int right, int pivot, int[] array) {
int curLeft = left - 1;
int curRight = right;
while(true){
while(array[++curLeft] > pivot)
;

while(curRight > left && array[--curRight] < pivot)
;

if(curLeft >= curRight){
break;
}else{
swap(curRight, curLeft, array);
}
}
swap(right, curLeft, array);

return curLeft;

}
``````

### 三项取中快速排序

``````private static void fastMid(int[] array){
fastMidCort(0, array.length - 1, array);
}

private static void fastMidCort(int left, int right, int[] array) {
if(right - left < 3){
lessSort(left, right, array);
}else{
int pivot = calcMid(left, right, array);
int border = findBorderMid(left, right, pivot, array);
fastMidCort(left, border - 1, array);
fastMidCort(border + 1, right, array);
}
}

private static int findBorderMid(int left, int right, int pivot, int[] array) {
int curLeft = left;
int curRight = right - 1;
while(true){
while (array[++left] > pivot)
;
while(array[--right] < pivot)
;

if(curLeft >= curRight){
break;
}else {
swap(curLeft, curRight, array);
}
}
swap(curLeft, right - 1, array);
return curLeft;
}

private static void lessSort(int left, int right, int[] array) {
if(right <= left){
return;
}else if(right - left < 2){
if(array[left] < array[right]){
swap(left, right, array);
}
}else{
if(array[left] < array[left + 1]){
swap(left, left + 1, array);
}
if(array[left] < array[right]){
swap(left, right, array);
}
if(array[left + 1] < array[right]){
swap(left + 1, right, array);
}
}
}

private static void swap(int a, int b, int[] array) {
int t;
t = array[b];
array[b] = array[a];
array[a] = t;
}
``````

×