35：冒泡、选择、插入排序
能手写排序算法，能求时间、空间复杂度，排序算法稳定性
能了解各算法的优缺点，根据场景选择合适的算法。
能优化排序算法，了解细节。
1. 冒泡排序
冒泡排序：思想：【相邻两个数进行比较】，如果前面的比后面的大，就进行交换; 否则不需要交换. 大的往上冒
第一趟结束后，最大值到了最后面。
第二趟结束后，次大值移动到未排序列表的最后面。
直到都排序完成。
#include <jni.h>
#include <string>
#include <android/log.h>
#include "ArrayUtil.cpp"
// 补讲一个知识点
// 结构体区别名
#define TAG "TAG"
// 对方法进行 define LOGE(...参数) -> __android_log_print(ANDROID_LOG_ERROR, TAG, __VA_ARGS__)
// 重要一个点
#define LOGE(...) __android_log_print(ANDROID_LOG_ERROR, TAG, __VA_ARGS__)
// 其他方法的定义 __android_log_print 取了一个别名 （参数固定，可变）
using namespace std;
// 冒泡排序：思想：相邻两个数进行比较，如果前面的比后面的大，就进行交换，否则不需要交换
// 能写， 求时间复杂度，空间复杂度 时间复杂度：O（n²）≈ O(n*(n-1)/2)
// 能优化冒泡排序 下周 ，网上有两种优化方法 作业 （鸡尾酒排序TODO，记录标志位-看内存是否有交换）
// 第三种思路：遍历的过程中可以记录一下位置（TODO） 思想要了解
void bubbleSort(int arr[], int len) {
for (int i = 0; i < len - 1; ++i) { // 外层循环：n-1 步
// j < len - i - 1
for (int j = 0; j < len - i - 1; ++j) { // 内层循环：n-1, n-2 ,n-3, ..., 1
if (arr[j] > arr[j + 1]) { // 上面的-1，因为这边+1会导致角标越界。
// 交换 一次交换是三次赋值
std::swap(arr[j], arr[j + 1]);
}
}
}
}
// 2.标记位法：
// bool exchange = fasle;
// 内存循环中，有交换，exchange = true; 一次内循环结束后。
// 外层循环中，判断，如果没交换（排序好的），break跳出循环（不要再交换排序了）。
// ***选择排序：思想 遍历找出最小的位置，最后与第一个位置进行交换 空间复杂度：O(1)
void selectSort(int arr[], int len) { // 升序排序。
for (int i = 0; i < len; ++i) {
int min = i; // 索引值，然后根据索引值交换。
for (int j = i + 1; j < len; ++j) {
if (arr[min] > arr[j]) {
min = j; // 1.找到最小值的位置 index
}
}
swap(arr[i], arr[min]); // 2. min位置 与 第0（i）位置进行交换。以达到排序
}
}
void print_array(int arr[], int len) {
for (int i = 0; i < len; ++i) {
// 这个方法比较复杂 __android_log_print(ANDROID_LOG_ERROR, "TAG", "%d", arr[i]);
LOGE("%d", arr[i]);
}
}
extern "C"
JNIEXPORT jstring
JNICALL
Java_com_darren_ndk_day35_MainActivity_stringFromJNI(
JNIEnv *env,
jobject /* this */) {
// 测试, 取时间 ， 两个算法
int len = 20000;
int *arr = ArrayUtil::create_random_array(len, 20, 10000);
int *arr1 = ArrayUtil::copy_random_array(arr,len);
ArrayUtil::sort_array("bubbleSort", bubbleSort, arr, len);// 6
ArrayUtil::sort_array("selectSort", selectSort, arr1, len);// 3
// ? 思考 3 次课 ，冒泡的优化，插入排序，希尔排序，怎样去看 log 日志 O(n平方)
delete[](arr); // 删除int[], 释放内存。
delete[](arr1);
// 对性能进行测试 看错误日志
std::string hello = "Hello from C++";
return env->NewStringUTF(hello.c_str());
}
2.方法的宏定义（取别名）
#define TAG "TAG"
#define printT(number) print(TAG, int number);
void print(char* tag, int number){}
↓ 打印优化，重定义。可变参数...要听换成 __VA_ARGS__
#define LOGE(...) __android_log_print(ANDROID_LOG_ERROR, TAG, __VA_ARGS__)
// 前两各参数固定，后面的参数，使用格式化。
4.排序方案比较
冒泡排序：1次交换是3次赋值。
选择排序：不断比较记录，每次循环只有1次交换。
ArrayUtil.cpp
#include <stdlib.h>
#include <android/log.h>
#include <time.h>
#include <assert.h>
#define TAG "TAG"
// __VA_ARGS__ 固定写法
#define LOGE(...) __android_log_print(ANDROID_LOG_ERROR, TAG, __VA_ARGS__)
namespace ArrayUtil {
// 创建一定范围的随机(low,high)数数组 返回。
int *create_random_array(int len, int low, int high) {
int *arr = new int[len];
for (int i = 0; i < len; ++i) {
arr[i] = rand() % (high - low) + low;
}
return arr;
}
// arr拷贝
int *copy_random_array(int *arr, int len) {
int *copy_arr = new int[len];
memcpy(copy_arr, arr, sizeof(int) * len);
return copy_arr;
}
// 排序算法传进来，指针回调。函数指针怎么定义。
void sort_array(char *sortName, void(*sort)(int *, int), int *arr, int len) {
size_t start_time = clock();
sort(arr, len); // 排序
size_t end_time = clock();
// 计算算法的执行时间
double time = static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC;
LOGE("排序方法 %s的执行时间：%lf", sortName, time);
// 检测这个数组有没有拍好序
for (int i = 0; i < len - 1; ++i) {
assert(arr[i] <= arr[i + 1]);
}
}
}
