Skip to content

Instantly share code, notes, and snippets.

@liaohuqiu
Created June 10, 2018 08:17
Show Gist options
  • Save liaohuqiu/71d9315b1e10ee30f29b3069fda76c6b to your computer and use it in GitHub Desktop.
Save liaohuqiu/71d9315b1e10ee30f29b3069fda76c6b to your computer and use it in GitHub Desktop.
package kxi.rpc.test.basic;
class MergeSortSolution {
private static void merge(int arr[], int left, int mid, int right) {
int leftCount = mid - left + 1;
int rightCount = right - mid;
int leftArr[] = new int[leftCount];
int rightArr[] = new int[rightCount];
for (int i = 0; i < leftCount; ++i) {
leftArr[i] = arr[left + i];
}
for (int j = 0; j < rightCount; ++j) {
rightArr[j] = arr[mid + 1 + j];
}
int leftPoint = 0, rightPoint = 0;
int point = left;
while (leftPoint < leftCount && rightPoint < rightCount) {
if (leftArr[leftPoint] <= rightArr[rightPoint]) {
arr[point] = leftArr[leftPoint];
leftPoint++;
} else {
arr[point] = rightArr[rightPoint];
rightPoint++;
}
point++;
}
while (leftPoint < leftCount) {
arr[point] = leftArr[leftPoint];
leftPoint++;
point++;
}
while (rightPoint < rightCount) {
arr[point] = rightArr[rightPoint];
rightPoint++;
point++;
}
}
public static void sort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
}
package kxi.rpc.test.basic;
class QuickSortSolution {
private static int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
private static void swap(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment