常见的排序算法
- 以下排序算法全部按照从小到大排列。
- 冒泡排序
- 相邻两个数依次进行比较，一次循环结束后，最大的值会被移到最后一个位置。
- 选择排序
- 选择一个数，然后依次和数组中的数比较，如果遇到比这个数小的，就交换位置或者记录下标（最后交换）。
- 快速排序
- 1.在数据集之中，选择一个元素作为”基准”（pivot）。
- 2.所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。这个操作称为分区 (partition) 操作,分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
- 3.对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
1.冒泡排序
public class BubbleSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] array = { 4, 7, 8, 2, 17, 33, 2, 11, 2, 3, 45, 77, 88, 16, -1 };
bubbleSort(array);
print(array);
}
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
}
}
}
}
public static void print(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
public static void swap(int[] array, int a, int b) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
}
2.选择排序
public class SelectSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] array = { 4, 3, 8, 2, 17, 33, 2, 11, 2, 3, 45, 77, 88, 16, -1 };
selectSortMethod01(array);
print(array);
selectSortMethod02(array);
print(array);
}
public static void selectSortMethod01(int[] array) {
// 每次都和后一个数进行比较，如果比他小，就马上交换位置,交换次数比较多
for (int i = 0; i < array.length - 1; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[i] > array[j])
swap(array, i, j);
}
}
}
public static void selectSortMethod02(int[] array) {
// 记录数组下标，如果找到比他小的，就记录下标，不用马上交换，一次循环结束后在交换
for (int i = 0; i < array.length - 1; i++) {
int min = i;
for (int j = i + 1; j < array.length; j++) {
if (array[i] > array[j])
min = j;
}
swap(array, min, i);
}
}
public static void print(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
public static void swap(int[] array, int a, int b) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
}
3.快速排序
public class QuickSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] array = { 4, 7, 8, 2, 17, 33, 2, 11, 2, 3, 45, 77, 88, 16, -1 };
quickSortMethod01(array, 0, array.length - 1);
print(array);
quickSortMethod02(array, 0, array.length - 1);
print(array);
}
public static void quickSortMethod01(int[] array, int left, int right) {
if (left < right) {
// 选择数组中第一个数作为pivotValue
int pivotIndex = left;
int storeIndex = pivotIndex + 1;
int pivotValue = array[pivotIndex];
for (int i = storeIndex; i <= right; i++) {
if (array[i] < pivotValue) {
swap(array, i, storeIndex);
storeIndex++;
}
}
storeIndex--;
swap(array, storeIndex, pivotIndex);
quickSortMethod01(array, left, storeIndex - 1);
quickSortMethod01(array, storeIndex + 1, right);
}
}
public static void quickSortMethod02(int[] array, int left, int right) {
if (left < right) {
// 选择数组中最后一个数作为pivotValue
int pivotIndex = right;
int pivotValue = array[pivotIndex];
int storeIndex = left;
for (int i = storeIndex; i <= right - 1; i++) {
if (array[i] < pivotValue) {
swap(array, storeIndex, i);
storeIndex++;
}
}
swap(array, pivotIndex, storeIndex);
quickSortMethod02(array, left, storeIndex - 1);
quickSortMethod02(array, storeIndex + 1, right);
}
}
public static void print(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
public static void swap(int[] array, int a, int b) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
}
参考资料
