冒泡排序:
从小到大:
取数据A[0]将其与其后面的数据A[1]、A[2]、A[3]…等数据比较,遇到比A[0]更小的数就交换数值,再继续用A[0]和后面的数据比较,这样下来A[0]一定是这组数中最小的了。之后再取A[1]、A[2]、A[3]…等数据比较,和A[0]一样,A[1]最后成为剩下数据中最小的那一个…如此往复,直到排序结束。
Code:
template<typename T, unsigned char SIZE>
void Data<T, SIZE>::bubble_smalltobig()
{
cout << "**********************Bubble:small to big*******************************" << endl;
unsigned char i, j;
/*遇到小的马上交换,交换后,用小的继续和下面的数比较,边比较(轮询)边换位*/
for(i = 0; i < SIZE; i++)
{
for(j = i + 1; j < SIZE; j++)
{
if(data[i] > data[j])
{
/*i、j互换也可以实现交换*/
data[j] ^= data[i];
data[i] = data[j] ^ data[i];
data[j] ^= data[i];
}
}
}
for(i = 0; i < SIZE; i++)
{
cout << data[i] << " ";
}
if(i == SIZE)
{
cout << endl;
}
}
选择排序:
从大到小:
取数据A[0],记录其下角标‘0’,并将其与后面的数据A[1]、A[2]、A[3]…等数据进行比较,遇到比A[0]更小的数则将A[0]的下角标记录并替换掉,继续用新的A[新下角标值]和后面的A[5]、A[6]、A[7]等数据比较,有更小的数则同样记录并替换,最后得到一个最小数据对应的下角标,如果这个下角标和‘0’不同,则进行交换,至此A[0]中将是这组数据中最小的一个。接着对A[1]也进行新一轮的判别,记录下角标‘1’…..如此循环往复,直到排序完成。
Code:
template<typename T, unsigned char SIZE>
void Data<T, SIZE>::select_bigtosmall()
{
cout << "****************************Select:big to small**********************************" << endl;
unsigned char i,j;
unsigned char note = 0;//记录最大数的下角标
/*先轮询一边,记录最大的数的下角标,之后在换位*/
for(i = 0; i < SIZE ; i++)
{
note = i;
for(j = i + 1; j < SIZE; j++)
{
if(data[note] < data[j])
note = j;
}
if(note != i)
{
data[i] ^= data[note];
data[note] = data[i] ^ data[note];
data[i] ^= data[note];
}
}
for(i = 0; i < SIZE; i++)
{
cout << data[i] << " ";
}
if(i == SIZE)
{
cout << endl;
}
}
插入排序:
从大到小:
数据A:45 35 84 1 36
首先假设45是已经排好序的,则取35,和A[0]比较,比45小则不动作,此时45和35也已经可以看做是一个从大到小的小的排序序列了45 35 84 1 36
然后再取84先和A[0]比较,发现84比A[0]大,则进行移位排序,排序后序列为84 45 35 1 36
再取1和A[0]比较,比84小,不触发排序,和A[1]比较,同样也不触发排序,和A[2]比较,依然没有触发排序,所以1原地不动84 45 35 1 36
再取36,和A[0]比较,比84小,不触发排序,和A[1]比,还是小,不触发排序,和A[2]比,比35大,触发排序移位,注意此时已经没有必要再和35后面的数比较了,因为35已经是之后的一段数中最大的了,所以要用break,最后84 45 36 35 1至此完成排序
Code:
template<typename T, unsigned char SIZE>
void Data<T, SIZE>::insert_bigtosmall()
{
cout << "*************************Insert:big to small*************************" << endl;
int i,j,k = 0;
T temp;
/*取一个数去和可能插入的左方的数比较,如果该数大于左方的被比较数则移位,因为保证了之前就是大到小排列,所以排完一次就break*/
for(i = 1; i < SIZE; i++)
{
temp = data[i];
for(j = 0; j < i ; j++)
{
if(data[i] > data[j])
{
for(k = i - 1; k >= j; k--)
{
data[k+1] = data[k];
}
data[j] = temp;
break;
}
}
}
for(i = 0; i < SIZE; i++)
{
cout << data[i] << " ";
}
if(i == SIZE)
{
cout << endl;
}
}
快速排序:
1、定中轴(一般取第一个数)
2、从后往前:找出后面更小的数放前面(第一个数处),同时前面的下角标自加
3、从前往后:找出前面更大的数放后面(最后一个数处),同时后面下角标自减
4、递归调用:利用中轴,分别进行前后两边的排序,递归结束条件 high<=low
Code:
unsigned char quick(int *a, unsigned char low, unsigned char high)
{
int temp = 0;
temp = a[low];
while(low < high)
{
/*从后面开始找出小的放前面*/
while(low < high && a[high] >= temp)
{
high--;
}
if(low < high)
{
a[low] = a[high];
low++;
}
/*从前面开始找出大的放后面*/
while(low < high && a[low] < temp)
{
low++;
}
if(low < high)
{
a[high] = a[low];
high--;
}
a[low] = temp;
}
return low;
}
void quicksort(int a[], unsigned char low, unsigned char high)
{
unsigned char temp = 0;
if(low < high)
{
temp = quick(a, low, high);//先分两半
quicksort(a, temp+1, high);//对后半部分排序
quicksort(a, low, temp-1);//对前半部分排序
}
}