the producer 1 wrote data 96,where 0 the producer 0 wrote data 73,where 1 the consumer 1 read the data 96,from 0 the consumer 0 read the data 73,from 1 the producer 0 wrote data 54,where 2 the producer 1 wrote data 63,where 3 the consumer 0 read the data 54,from 2 the consumer 2 read the data 63,from 3 the producer 1 wrote data 22,where 4 the producer 0 wrote data 60,where 5 the consumer 1 read the data 22,from 4 the consumer 0 read the data 60,from 5 the producer 0 wrote data 20,where 6 the producer 1 wrote data 47,where 7 the consumer 1 read the data 20,from 6 the consumer 2 read the data 47,from 7 the producer 1 wrote data 7,where 8 the producer 0 wrote data 46,where 9 the consumer 1 read the data 7,from 8 the consumer 0 read the data 46,from 9 the producer 0 wrote data 32,where 0 the producer 1 wrote data 96,where 1 the consumer 0 read the data 32,from 0 the consumer 2 read the data 96,from 1 the producer 1 wrote data 61,where 2 the producer 0 wrote data 35,where 3 the consumer 0 read the data 61,from 2 the consumer 1 read the data 35,from 3 the producer 0 wrote data 29,where 4 the producer 1 wrote data 54,where 5 the consumer 0 read the data 29,from 4 the consumer 2 read the data 54,from 5 the producer 1 wrote data 85,where 6 the producer 0 wrote data 20,where 7 the consumer 0 read the data 85,from 6 the consumer 1 read the data 20,from 7 the producer 0 wrote data 13,where 8 the producer 1 wrote data 71,where 9 the consumer 0 read the data 13,from 8 the consumer 2 read the data 71,from 9 the producer 0 wrote data 4,where 0 the producer 1 wrote data 94,where 1 the consumer 0 read the data 4,from 0 the consumer 1 read the data 94,from 1 the producer 1 wrote data 70,where 2 the producer 0 wrote data 99,where 3 the consumer 0 read the data 70,from 2 the consumer 2 read the data 99,from 3 ...
实现线程的三种模式
纯粹的用户级线程
纯粹的内核级线程
组合
区别
用户级
创建开销小，可以创建很多。
无法使用多个处理器
内核级
创建开销大。
由内核直接管理
可以使用多个处理器
线程安全
查看线程信息的方法
1 2 3
ps -ef | grep main ps -eLf | grep main #UID PID PPID LWP（线程ID） C NLWP（线程数目） ps -L #显示线程id
voidselection_sort(int a[], int n) { for (int i = 0; i < n; ++i) { int min_idx = i; for (int j = i + 1; j < n; ++j) { if (a[j] < a[min_idx]) { min_idx = j; } } // 注意，是 a[i]而不是a[j] 和 a[min_idx]交换 swap(&a[i], &a[min_idx]); } }
1 2 3 4 5 6 7 8 9 10 11 12 13
i min 0 1 2 3 4 5 6 7 8 9 10 S O R T E X A M P L E 0 6 S O R T E X A M P L E 1 4 A O R T E X S M P L E 2 10 A E R T O X S M P L E 3 9 A E E T O X S M P L R 4 7 A E E L O X S M P T R 5 7 A E E L M X S O P T R 6 8 A E E L M O S X P T R 7 10 A E E L M O P X S T R 8 8 A E E L M O P R S T X 9 9 A E E L M O P R S T X 10 10 A E E L M O P R S T X
优化：第一层for中的i可以优化为i < n - 1，因为排最后一个时，剩余序列就1个数了，无需再找最小了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
voidselection_sort(int a[], int n) { int min_idx; for(int i = 0; i < n - 1; ++i) { min_idx = i; for(int j = i + 1; j < n; ++j) { if(a[j] < a[min_idx]) { min_idx = j; } } swap(&a[i], &a[min_idx]); } }
voidquick_sort(int a[], int left, int right) { if (left >= right) return; int pivot = a[left]; int i = left; int j = i + 1; // j 遍历向右 while (j <= right) { if (a[j] <= pivot) { swap(&a[i + 1], &a[j]); ++i; } ++j; } // i 的位置是 左侧部分的末尾。 // left 属于 左侧部分。不应与i+1交换，而是与i交换 swap(&a[i], &a[left]); // i 的位置是基准值，已固定。只需排除了i之后剩下的。 quick_sort(a, left, i - 1); quick_sort(a, i + 1, right); }
优化：if (a[j] <= pivot)中最好把<=改为<。
优化前，如果数组中等值太多，则会进行多次无意义的交换。
设数组全是相同值，选左端为轴。
对每个 j，a[j] <= pivot 都成立，于是 i 每次自增，循环结束后 i == right，最后再把 pivot 和 a[i] 交换——轴被放到最右端。
voidquick_sort(int a[], int left, int right) { if (left >= right) return; int pivot = a[left]; int i = left; int j = i + 1; // j 遍历向右 while (j <= right) { if (a[j] < pivot) { swap(&a[i + 1], &a[j]); ++i; } ++j; } // i 的位置是 左侧部分的末尾。 // left 属于 左侧部分。不应与i+1交换，而是与i交换 swap(&a[i], &a[left]); // i 的位置是基准值，已固定。只需排除了i之后剩下的。 quick_sort(a, left, i - 1); quick_sort(a, i + 1, right); }
voidquick_sort(int a[], int left, int right) { if (left >= right) return; int pivot = a[left]; int i = left; int j = right; while (i < j) { while (i < j && a[j] > pivot) { --j; } if (i < j) // a[right] <= pivot { a[i] = a[j]; } while (i < j && a[i] <= pivot) { ++i; } if (i < j) // a[left] >= pivot { a[j] = a[i]; } } a[i] = pivot; quick_sort(a, left, i - 1); quick_sort(a, i + 1, right); }
//另外，此方法不能交换划分顺序！即必须先左划分，后右划分，否则错误！ voidquick_sort(int a[], int left, int right) { if (left >= right) return; //此时若只有两个元素，则出现l == r int l = left, pivot = right, r = right - 1; while (l < r) { if (a[l] <= a[pivot]) ++l; elseif (a[r] > a[pivot]) --r; else swap(&a[l], &a[r]); } if (a[l] > a[pivot]) { swap(&a[l], &a[pivot]); pivot = l; } quick_sort(a, left, pivot - 1); quick_sort(a, pivot + 1, right); }
8：右尾、双向、先右后左划分；（仿照“左首、双向先左后右划分”《算法》写的）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
voidquick_sort(int a[], int left, int right) { if (left >= right) return; int i = left - 1, j = right;//为了便于下面++i和--j的代码统一性，所以从left-1到right，实际上只考察到了left到right-1的部分 int pivot = a[right]; while (1) { while (a[--j] > pivot) if (j == left) break; while (a[++i] <= pivot) if (i == right) break; if (i >= j) break; swap(&a[i], &a[j]); } swap(&a[right], &a[i]);// a[right]为右尾元素，即基准值 //必须和a[i]交换，否则不对 quick_sort(a, left, i - 1); // 必须是i - 1，否则不对 quick_sort(a, i + 1, right);// 必须是i + 1，否则不对 }
其实我们发现，先左后右划分也正确，但是后三句中的基准位置是i，不能是j
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
voidquick_sort(int a[], int left, int right) { if (left >= right) return; int i = left - 1, j = right;//为了便于下面++i和--j的代码统一性，所以从left-1到right，实际上只考察到了left到right-1的部分 int pivot = a[right]; while (1) { while (a[++i] <= pivot) if (i == right) break; while (a[--j] > pivot) if (j == left) break; if (i >= j) break; swap(&a[i], &a[j]); } swap(&a[right], &a[i]);// a[right]为右尾元素，即基准值 //必须和a[i]交换，否则不对 quick_sort(a, left, i - 1); // 必须是i - 1，否则不对 quick_sort(a, i + 1, right);// 必须是i + 1，否则不对 }
intPartition(int * ar, int left, int right) { int i = left; int j = right; int pivot = ar[left]; while (i < j) { while (i < j && ar[j] > pivot) { --j; } if (i < j) // ar[j] <= pivot { ar[i] = ar[j]; } while (i < j && ar[i] <= pivot) { ++i; } if (i < j) { ar[j] = ar[i]; } } ar[i] = pivot; return i; } voidQuickSort(int * ar, int n) { std::queue<int> qu; qu.push(0); qu.push(n - 1); while (!qu.empty()) { int left = qu.front(); qu.pop(); int right = qu.front(); qu.pop(); int mid = Partition(ar, left, right); if (left < mid - 1) { qu.push(left); qu.push(mid - 1); } if (mid + 1 < right) { qu.push(mid + 1); qu.push(right); } } }
优化：随机基准或三位取中
优化：尾递归消除
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
// partition 返回轴最终下标 p；两侧为 [left, p-1] 与 [p+1, right] voidquick_sort(int a[], int left, int right) { while (left < right) { int p = partition(a, left, right); // 任选 Lomuto/挖坑，保证返回轴位 p // 递归较小一侧，较大一侧用循环“缩区间” if (p - left < right - p) { quick_sort(a, left, p - 1); // 小的那半递归 left = p + 1; // 大的那半转为尾部迭代 } else { quick_sort(a, p + 1, right); right = p - 1; } } }
// 三数取中：把 a[left], a[mid], a[right] 排成 a[left] <= a[mid] <= a[right]，然后把中位数放到 left 当轴 staticinlinevoidmedian_of_three_to_left(int a[], int left, int right) { int mid = left + ((right - left) >> 1); if (a[mid] < a[left]) swap_int(&a[mid] , &a[left]); if (a[right] < a[left]) swap_int(&a[right], &a[left]); if (a[right] < a[mid]) swap_int(&a[right], &a[mid]); // 此时 a[left] <= a[mid] <= a[right]，取中位数作为轴：交换到 left swap_int(&a[left], &a[mid]); } // 快速排序（挖坑法 + 尾递归消除 + 小区间插排 + 三数取中选轴） voidquick_sort(int a[], int left, int right) { while (left < right) { // 小区间用插入排序更快 if (right - left + 1 <= INSERTION_SORT_THRESHOLD) { insertion_sort(a, left, right); return; // 当前区间完成，直接返回（外层 while 退出） }
// 选轴优化：三数取中，并将中位数放到 left median_of_three_to_left(a, left, right);
// 分区 int p = partition_pit(a, left, right);
// 尾递归消除：总是递归较小的一侧，较大的一侧改为迭代 if (p - left < right - p) { quick_sort(a, left, p - 1); // 递归较小段 left = p + 1; // 大段转为下一轮循环 } else { quick_sort(a, p + 1, right); right = p - 1; } } }