1 基础算法

1.1快速排序

核心思想-三步走

1. 确定分界点：q[l], q[(l+r)/2], q[r], 随机
2. 调整区间
3. 递归处理

C代码

#include <stdio.h>


const int N=1e5+5;
int num[N];


void quickSort(int q[],int l,int r) {

	//如果只有一个元素或者达到边界  递归终止
	if (l >= r) return;

	int i = l - 1, j = r + 1, x = q[(l + r )/2];
	while (i < j) {
		do {
			i ++ ;
		} while (q[i] < x);

		do {
			j -- ;
		} while (q[j] > x);

        //交换两个数的值 
		if (i < j) {
			int tmp=num[i];
			num[i]=num[j];
			num[j]=tmp;
		//	swap(q[i], q[j]);
		}
	}
	
	//递归 
	quickSort(q, l, j);
	quickSort(q, j + 1, r);


}



int main() {
	int n;
	scanf("%d",&n);

	for(int i=0; i<n; i++) {
		scanf("%d",&num[i]);
	}
	int l,r;
	l=0;
	r=n-1;
	quickSort(num,l,r);

	for(int i=0; i<n; i++) {
		printf("%d ",num[i]);
	}

	return 0;
}

Java代码

package com.my.test;

import java.util.Scanner;

public class Task1_quickSort {

  public static void quickSort(int[] q, int l, int r) {
	  //递归的边界
			if(l>=r)
				  return ;
			
			int i = l - 1, j = r + 1, x = q[(l + r) / 2];
			
			
			while (i < j) {
				do {
					i++;
				} while (q[i] < x);
				do {
					j--;
				} while (q[j] > x);

				//两数交换
				if (i < j) {
					int tmp = q[i];
					q[i] = q[j];
					q[j] = tmp;
				}
			}

			//递归  左右两组进行快排
			quickSort(q, l, j);
			quickSort(q, j + 1, r);

		}
	
	
	public static void main(String[] args) {
		// 快速排序
		int n;
		Scanner sc = new Scanner(System.in);	 
		n = sc.nextInt();
		int num[] = new int[n+1];

		for (int i = 0; i < n; i++) {
			num[i] = sc.nextInt();
		}

		quickSort(num, 0, n - 1);

		for (int i = 0; i < n; i++) {
			System.out.print(num[i] + " ");
		}
		
		sc.close();
	}

}