常见基础排序算法总结及java代码

常见基础排序算法

常见的排序：

• 冒泡排序
• 快排
• 归并排序
• 插入排序
• 堆排序
• 选择排序
• 希尔排序
• 基数排序

---

冒泡排序

// java 
public static void bubblesort(int[] array) {        
int temp;

for(int end = array.length - 1; end > 0; end--) {
for(int i = 1; i <= end; i++)
if(array[i-1] > array[i]) {
                    temp = array[i];
array[i] = array[i-1];
array[i-1] = temp;
                }
        }
    }

快排

    /**
 * version 1 quickSort
 * @param arr
 * @param left
 * @param right
 */
public static void quickSort_02(int[] arr, int left, int right) {
if(left < right) {
int index = partition_02(arr, left, right);
            quickSort_02(arr, left, index - 1);
            quickSort_02(arr, index + 1, right);
        }
    }

private static int partition_02(int[] arr, int left, int right) {
int v = arr[right];
int i = left - 1;

for(int j = left; j < right; j++) {
if(arr[j] <= v) {
                i++;
                swap(arr, i, j);
            }
        }

        swap(arr, i + 1, right);

return i;
    }

    /**
 * version 2
 * @param arr
 * @param left
 * @param right
 */
public static void quickSort_01(int arr[], int left, int right) {
int index = partition(arr, left, right);
if(left < index - 1) { // Sort left half
            quickSort_01(arr, left, index - 1);
        }
if(index < right) { // Sort right half
            quickSort_01(arr, index, right);
        }
    }

public static int partition(int arr[], int left, int right) {
int pivot = arr[(left + right) / 2]; // Pick pivot point
while(left <= right) {
// Find element on left that should be on right
while(arr[left] < pivot)  left++;
// Finde element on right that should be on left
while(arr[right] > pivot) right--;

// Swap elements, and move left and right indices
if(left <= right) {
                swap(arr, left, right); // Swaps elements
                left++;
                right--;
            }
        }
return left;
    }

public static void swap(int[] arr, int left, int right) {
int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

归并排序

    public static void mergesort(int[] array) {
int[] helper = new int[array.length];
        mergesort(array, helper, 0, array.length - 1);
    }

public static void mergesort(int[] array, int[] helper, int low, int high) {
if(low < high) {
int middle = (low + high) / 2;
            mergesort(array, helper, low, middle); // Sort left half
            mergesort(array, helper, middle+1, high); // Sort right half
            merge(array, helper, low, middle, high); //Merge them
        }
    }

public static void merge(int[] array, int[] helper, int low, int middle, int high) {
/* Copy both halves into a helper array */
for(int i = low; i <= high; i++) {
            helper[i] = array[i];
        }

int helperLeft = low;
int helperRight = middle + 1;
int current = low;

/* Iterate through helper array. Compare the left and right
 * half, copying back the smaller element from the two halves
 * into the original array. 
 */
while(helperLeft <= middle && helperRight <= high) {
if(helper[helperLeft] <= helper[helperRight]) {
                array[current] = helper[helperLeft];
                helperLeft++;
            } else { // If right element is smaller than left element
                array[current] = helper[helperRight];
                helperRight++;
            }
            current++;
        }

/* Copy the rest of the left side of the array into the
 * target array. 
 */
int remaining = middle - helperLeft;
for(int i = 0; i <= remaining; i++) {
            array[current + i] = helper[helperLeft + i];
        }
    }

插入排序

    public static void insertionSort(int[] data) {
for(int index = 1; index < data.length; index++) {
int key = data[index];   // key 
int position = index;   // position

// shift larger values to the right
while(position > 0 && data[position-1] > key) {
                data[position] = data[position-1];
                position--;
            }
            data[position] = key;
        }
    }

堆排序

    private static int leftChild(int i) {
return 2 * i + 1;
    }

private static void percDown(int[] a, int i, int n) {
int child;
int tmp;

for(tmp = a[i]; leftChild(i) < n; i = child) {
            child = leftChild(i);

if(child != n - 1 && a[child] < a[child + 1]) 
                child++;
if(tmp < a[child]) 
                a[i] = a[child];
else
break;
        }

        a[i] = tmp;
    }

public static void heapSort(int[] a) {
for(int i = a.length / 2 - 1; i >= 0; i--) 
            percDown(a, i, a.length);

for(int i = a.length - 1; i > 0; i--) {
            swap(a, 0, i);
            percDown(a, 0, i);
        }
    }

private static void swap(int[] a, int i, int j) {
int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

希尔排序

基数排序

---