Skip to content

Instantly share code, notes, and snippets.

View XcqRomance's full-sized avatar

XcqRomance XcqRomance

View GitHub Profile
@XcqRomance
XcqRomance / BubbleSort.c
Created November 13, 2018 12:45
冒泡排序 时间复杂度:O(n^2) 空间复杂度:O(1),原地排序 稳定排序
// 冒泡排序 反复交换相邻的未按照次序排列元素
// 一组数中,相邻的两个数进行比较、交换,将最大(小)数交换至尾(首)部,即完成了一次冒泡排序
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);
}
}
}
@XcqRomance
XcqRomance / SelectionSort.c
Created November 13, 2018 14:13
选择排序 时间复杂度:O(n^2) 空间复杂度:O(1) 不稳定排序:排序算法的稳定性:通俗地讲就是能保证排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同。
// 选择排序 找到最小元素的角标位置
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);
@XcqRomance
XcqRomance / QuickSort.c
Created November 13, 2018 14:13
快速排序 时间复杂度:元素互异时间复杂度O(n·logn),最坏情况时间复杂度O(n^2); 空间复杂度:O(1),原址排序,但是递归需要使用空间 最优的情况下空间复杂度为:O(logn)  ;每一次都平分数组的情况,最差的情况下空间复杂度为:O( n );退化为冒泡排序的情况; 不稳定排序
// 快速排序
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);
}
@XcqRomance
XcqRomance / InsertSort.c
Created November 13, 2018 14:13
插入排序 时间复杂度:O(n^2) 空间复杂度:O(1),原地排序 稳定排序: 插入排序比冒泡排序更受欢迎:冒泡排序中的数据交换需要3个赋值语句,插入排序中的数据移动操作1个操作
// 插入排序 打扑克抓牌,左手是已经排好序的牌,右手是桌上的牌
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;
@XcqRomance
XcqRomance / MergeSort.c
Created November 13, 2018 14:13
归并排序 时间复杂度:O(n·logn); 空间复杂度:O(n) 稳定排序 分治法: 1.分解 2.解决 3.合并
// 归并排序 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));
@XcqRomance
XcqRomance / HeapSort.c
Created November 13, 2018 14:14
堆排序
// 维护堆的性质
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;
@XcqRomance
XcqRomance / BinarySerach.c
Created November 13, 2018 14:14
二分查找实现代码 注意点:1.循环退出条件low<=high而不是low<high;2.mid的取值,mid = (low + high) / 2;可能溢出,改进方法:mid = low + (high - low) / 2,极致优化,位运算:mid = low + ((high - low) >>1);3.low和high的更新
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;
@XcqRomance
XcqRomance / missingNumber.c
Created December 3, 2018 07:00
缺失数字
// 缺失数字 方法一使用求和公式-数组的各个元素之和
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;
}
// 缺失数字 方法二使用异或
@XcqRomance
XcqRomance / reverseBits.c
Created December 3, 2018 07:01
颠倒二进制位
// 颠倒二进制位
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;
@XcqRomance
XcqRomance / hammingWeight.c
Created December 3, 2018 07:01
位1的个数
// 位1的个数,
int hammingWeight(uint32_t n) {
int count = 0;
while (n) {
++count;
n = (n-1)&n;
}
return count;
}