This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 冒泡排序 反复交换相邻的未按照次序排列元素 | |
// 一组数中,相邻的两个数进行比较、交换,将最大(小)数交换至尾(首)部,即完成了一次冒泡排序 | |
void bubbleSort(int *arr,int arrSize) { | |
for (int i = 0 ; i < arrSize - 1; i++) { | |
for (int j = 1; j < arrSize - i; j++) { | |
if (arr[j-1] > arr[j]) { | |
swap(arr, j-1, j); | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 选择排序 找到最小元素的角标位置 | |
void selectionSort(int *arr,int arrSize) { | |
for (int i = 0 ; i < arrSize; i ++) { | |
int minIndex = i; | |
for (int j = i+1; j < arrSize; j++) { | |
if (arr[j]<arr[minIndex]) { | |
minIndex = j; | |
} | |
} | |
swap(arr, i, minIndex); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 快速排序 | |
int quickSortUnit(int *arr, int p, int r) { | |
int x = rand() % (r - p + 1) + p; // p到r以内的随机数 | |
swap(arr, x, r); // 交换随机出来的数和最后一数,作为主元 | |
int i = p-1; | |
for (int j = p; j <= r-1; j++) { | |
if (arr[j] <= arr[r]) { // 第r个元素作为主元元素 | |
i += 1; | |
swap(arr, i, j); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 插入排序 打扑克抓牌,左手是已经排好序的牌,右手是桌上的牌 | |
void inserSort(int *arr,int arrSize) { | |
for (int j = 1; j < arrSize; j++) { | |
int key = arr[j]; // 右手里拿的牌 | |
int i = j - 1; | |
while (i >= 0 && arr[i] > key) { // 左手已经排好序的牌和key进行比较 | |
arr[i+1] = arr[i]; | |
i--; | |
} | |
arr[i+1] = key; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 归并排序 arr带排序的数组 ,p开始index,q为中间切割index,r为数组末尾index | |
void mergeSortUnit(int *arr,int p,int q, int r) { | |
int n1 = q-p+1; // 子数组1的个数n1 | |
int n2 = r-q; // 子数组2的个数n2 | |
// 最后一位用来存饭哨岗值正无穷大 | |
int *leftArr = malloc((n1+1) * sizeof(int)); | |
for (int i = 0; i < n1; i++) { | |
leftArr[i] = arr[p + i]; | |
} | |
int *rightArr = malloc((n2+1) * sizeof(int)); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 维护堆的性质 | |
void maxHeapify(int *arr,int i,int heapSize) { | |
int left = i*2+1; | |
int right = i*2+2; | |
int largest; | |
if (left <= heapSize && arr[left] > arr[i]) { | |
largest = left; | |
} else { | |
largest = i; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
int bsearch(int[] a, int n, int value) { | |
int low = 0; | |
int high = n - 1; | |
while (low <= high) { | |
int mid = low + ((high - low) >>1); | |
if (a[mid] == value) { | |
return mid; | |
} else if (a[mid] < value) { | |
low = mid + 1; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 缺失数字 方法一使用求和公式-数组的各个元素之和 | |
int missingNumber(int* nums, int numsSize) { | |
int sum = 0; | |
for (int i = 0; i < numsSize; i++) { | |
sum += nums[i]; | |
} | |
return numsSize*(numsSize+1)/2 - sum; | |
} | |
// 缺失数字 方法二使用异或 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 颠倒二进制位 | |
uint32_t reverseBits(uint32_t n) { | |
uint32_t m=0; | |
for(int i=0;i<32;i++){ | |
m<<=1; | |
m=m|(n&1); | |
//m<<=1; | |
n>>=1;//必须是这样的顺序,m左移32位,如果在下面,左移了33位; | |
} | |
return m; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 位1的个数, | |
int hammingWeight(uint32_t n) { | |
int count = 0; | |
while (n) { | |
++count; | |
n = (n-1)&n; | |
} | |
return count; | |
} |
OlderNewer