1.冒泡排序
冒泡排序
public class BubbleSort{
public static void main(String[] args) {
int[] numbers=new int[]{1,5,8,2,3,9,4};
int i,j;
for(i=0;i<numbers.length-1;i++)
{
for(j=0;j<numbers.length-1-i;j++)
{
if(numbers[j]>numbers[j+1])
{
int temp=numbers[j];
numbers[j]=numbers[j+1];
numbers[j+1]=temp;
}
}
}
System.out.println("排序后的结果是:");
for(i=0;i<numbers.length;i++)
System.out.print(numbers[i]+" ");
}
}
2.快速排序
快速排序
public class QuickSort{
public static void quickSort(int[] arr, int low, int high) {
int i, j, temp, t;
if (low > high) {
return;
}
i = low;
j = high;
//temp就是基准位
temp = arr[low];
while (i < j) {
//先看右边，依次往左递减
while (temp <= arr[j] && i < j) {
j--;
}
//再看左边，依次往右递增
while (temp >= arr[i] && i < j) {
i++;
}
//如果满足条件则交换
if (i < j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort(arr, low, j - 1);
//递归调用右半数组
quickSort(arr, j + 1, high);
}
public static void main(String[] args) {
int[] arr = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
quickSort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
3.归并排序
image
public class MergeSort {
//两路归并算法，两个排好序的子序列合并为一个子序列
public void merge(int []a,int left,int mid,int right){
int []tmp=new int[a.length];//辅助数组
int p1=left,p2=mid+1,k=left;//p1、p2是检测指针，k是存放指针
while(p1<=mid && p2<=right){
if(a[p1]<=a[p2])
tmp[k++]=a[p1++];
else
tmp[k++]=a[p2++];
}
while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
while(p2<=right) tmp[k++]=a[p2++];//同上
//复制回原素组
for (int i = left; i <=right; i++)
a[i]=tmp[i];
}
public void mergeSort(int [] a,int start,int end){
if(start<end){//当子序列中只有一个元素时结束递归
int mid=(start+end)/2;//划分子序列
mergeSort(a, start, mid);//对左侧子序列进行递归排序
mergeSort(a, mid+1, end);//对右侧子序列进行递归排序
merge(a, start, mid, end);//合并
}
}
@Test
public void test(){
int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
mergeSort(a, 0, a.length-1);
System.out.println("排序完成的数组：");
for (int e : a)
System.out.print(e+" ");
}
}
4.插入排序
image
public class InsertSort {
public static void main(String[] args) {
int[] arr = {12,3,2345,645,756,867,8979,879,83,1,3,6,900,45};
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
insertSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
//插入排序
public static void insertSort(int[] arr) {
int insertVal = 0;
int insertIndex = 0;
for(int i = 1; i < arr.length; i++) {
insertVal = arr[i];
insertIndex = i - 1;
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
if(insertIndex + 1 != i) {
arr[insertIndex + 1] = insertVal;
}
}
}
}
5.选择排序
选择排序
public class SelectionSort {
public static void main(String[] args) {
int[] arr = {12,32,23,54,56,867,7,6,80};
selectionSort(arr);
}
public static int[] selectionSort(int[] array) {
if (array.length == 0 || array.length == 1) { return array;}
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i; j < array.length; j++) {
if (array[j] < array[minIndex])
minIndex = j;
}
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
return array;
}
}
6.两数之和
//一遍hash
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
//暴力破解
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == target - nums[i]) {
return new int[] { i, j };
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
