1、不用中間變量,用兩種方法交換A和B的值
// 1.中間變量
void swap(int a, int b) {
int temp = a;
a = b;
b = temp;
}
// 2.加法
void swap(int a, int b) {
a = a + b;
b = a - b;
a = a - b;
}
// 3.異或（相同為0，不同為1. 可以理解為不進位加法）
void swap(int a, int b) {
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
2、求最大公約數(shù)
/** 1.直接遍歷法 */
int maxCommonDivisor(int a, int b) {
int max = 0;
for (int i = 1; i <=b; i++) {
if (a % i == 0 && b % i == 0) {
max = i;
}
}
return max;
}
/** 2.輾轉(zhuǎn)相除法 */
int maxCommonDivisor(int a, int b) {
int r;
while(a % b > 0) {
r = a % b;
a = b;
b = r;
}
return b;
}
// 擴展：最小公倍數(shù) = (a * b)/最大公約數(shù)
3、模擬棧操作
- 棧是一種數(shù)據(jù)結(jié)構(gòu)婚温，特點：先進后出
- 練習(xí)：使用全局變量模擬棧的操作
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
//保護全局變量：在全局變量前加static后，這個全局變量就只能在本文件中使用
static int data[1024];//棧最多能保存1024個數(shù)據(jù)
static int count = 0;//目前已經(jīng)放了多少個數(shù)(相當(dāng)于棧頂位置)
//數(shù)據(jù)入棧 push
void push(int x){
assert(!full());//防止數(shù)組越界
data[count++] = x;
}
//數(shù)據(jù)出棧 pop
int pop(){
assert(!empty());
return data[--count];
}
//查看棧頂元素 top
int top(){
assert(!empty());
return data[count-1];
}
//查詢棧滿 full
bool full() {
if(count >= 1024) {
return 1;
}
return 0;
}
//查詢椣狈瘢空 empty
bool empty() {
if(count <= 0) {
return 1;
}
return 0;
}
int main(){
//入棧
for (int i = 1; i <= 10; i++) {
push(i);
}
//出棧
while(!empty()){
printf("%d ", top()); //棧頂元素
pop(); //出棧
}
printf("\n");
return 0;
}
4栅螟、排序算法
選擇排序荆秦、冒泡排序、插入排序三種排序算法可以總結(jié)為如下：
都將數(shù)組分為已排序部分和未排序部分力图。
- 選擇排序?qū)⒁雅判虿糠侄x在左端步绸，然后選擇未排序部分的最小元素和未排序部分的第一個元素交換。
- 冒泡排序?qū)⒁雅判虿糠侄x在右端吃媒，在遍歷未排序部分的過程執(zhí)行交換瓤介，將最大元素交換到最右端。
- 插入排序?qū)⒁雅判虿糠侄x在左端赘那，將未排序部分元的第一個元素插入到已排序部分合適的位置刑桑。
4.1、選擇排序
- 【選擇排序】：最值出現(xiàn)在起始端
- 第1趟：在n個數(shù)中找到最小(大)數(shù)與第一個數(shù)交換位置
- 第2趟：在剩下n-1個數(shù)中找到最小(大)數(shù)與第二個數(shù)交換位置
- 重復(fù)這樣的操作...依次與第三個募舟、第四個...數(shù)交換位置
- 第n-1趟祠斧，最終可實現(xiàn)數(shù)據(jù)的升序（降序）排列。
void selectSort(int *arr, int length) {
for (int i = 0; i < length - 1; i++) { //趟數(shù)
for (int j = i + 1; j < length; j++) { //比較次數(shù)
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
4.2拱礁、冒泡排序
- 【冒泡排序】：相鄰元素兩兩比較琢锋，比較完一趟，最值出現(xiàn)在末尾
- 第1趟：依次比較相鄰的兩個數(shù)呢灶，不斷交換（小數(shù)放前吴超，大數(shù)放后）逐個推進，最值最后出現(xiàn)在第n個元素位置
- 第2趟：依次比較相鄰的兩個數(shù)鸯乃，不斷交換（小數(shù)放前鲸阻，大數(shù)放后）逐個推進，最值最后出現(xiàn)在第n-1個元素位置
- …… ……
- 第n-1趟：依次比較相鄰的兩個數(shù)缨睡，不斷交換（小數(shù)放前赘娄，大數(shù)放后）逐個推進，最值最后出現(xiàn)在第2個元素位置
void bublleSort(int *arr, int length) {
for(int i = 0; i < length - 1; i++) { //趟數(shù)
for(int j = 0; j < length - i - 1; j++) { //比較次數(shù)
if(arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
5宏蛉、折半查找（二分查找）
- 折半查找：優(yōu)化查找時間（不用遍歷全部數(shù)據(jù)）
- 折半查找的原理：
- 1> 數(shù)組必須是有序的
- 2> 必須已知min和max（知道范圍）
- 3> 動態(tài)計算mid的值，取出mid對應(yīng)的值進行比較
- 4> 如果mid對應(yīng)的值大于要查找的值性置，那么max要變小為mid-1
- 5> 如果mid對應(yīng)的值小于要查找的值拾并，那么min要變大為mid+1
// 已知一個有序數(shù)組, 和一個key, 要求從數(shù)組中找到key對應(yīng)的索引位置
int findKey(int *arr, int length, int key) {
int min = 0, max = length - 1, mid;
while (min <= max) {
mid = (min + max) / 2; //計算中間值
if (key > arr[mid]) {
min = mid + 1;
} else if (key < arr[mid]) {
max = mid - 1;
} else {
return mid;
}
}
return -1;
}
qq技術(shù)交流群
qq交流群.jpeg
作者微信公眾號
微信公眾號.jpg
